Рубрики

Найти минимальный элемент в отсортированном и повернутом массиве

Сортированный массив вращается в неизвестной точке, найдите в нем минимальный элемент.

Следующее решение предполагает, что все элементы различны.

Примеры:

Input: {5, 6, 1, 2, 3, 4}
Output: 1

Input: {1, 2, 3, 4}
Output: 1

Input: {2, 1}
Output: 1

Простое решение состоит в том, чтобы пройти весь массив и найти минимум. Это решение требует времени O (n).
Мы можем сделать это в O (Logn), используя бинарный поиск. Если мы поближе рассмотрим приведенные выше примеры, мы можем легко определить следующую схему:

  • Минимальный элемент — это единственный элемент, предыдущий элемент которого больше его. Если нет предыдущего элемента элемента, то нет вращения (первый элемент минимален). Мы проверяем это условие для среднего элемента, сравнивая его с (mid-1) 'th и (mid + 1)' элементами.
  • Если минимальный элемент не находится в середине (ни в середине, ни в середине + 1), то минимальный элемент находится либо в левой половине, либо в правой половине.
    1. Если средний элемент меньше, чем последний элемент, то минимальный элемент лежит в левой половине
    2. Еще минимальный элемент лежит в правой половине.

Мы настоятельно рекомендуем вам попробовать это самостоятельно, прежде чем вы увидите следующую реализацию.

C ++

// C ++ программа для поиска минимума
// элемент в отсортированном и повернутом массиве
#include <bits/stdc++.h>

using namespace std;

  

int findMin(int arr[], int low, int high) 

    // Это условие необходимо для

    // обрабатывать случай, когда массив не

    // вращается на всех

    if (high < low) return arr[0]; 

  

    // Если остался только один элемент

    if (high == low) return arr[low]; 

  

    // Найти середину

    int mid = low + (high - low)/2; / * (низкий + высокий) / 2; * /

  

    // Проверяем, является ли элемент (mid + 1) минимальным. Рассмотреть возможность

    // такие случаи, как {3, 4, 5, 1, 2}

    if (mid < high && arr[mid + 1] < arr[mid]) 

    return arr[mid + 1]; 

  

    // Проверяем, является ли середина минимальным элементом

    if (mid > low && arr[mid] < arr[mid - 1]) 

    return arr[mid]; 

  

    // Решаем, нужно ли нам идти в левую или правую половину

    if (arr[high] > arr[mid]) 

    return findMin(arr, low, mid - 1); 

    return findMin(arr, mid + 1, high); 

  
// Программа драйвера для проверки вышеуказанных функций

int main() 

    int arr1[] = {5, 6, 1, 2, 3, 4}; 

    int n1 = sizeof(arr1)/sizeof(arr1[0]); 

    cout << "The minimum element is " << findMin(arr1, 0, n1-1) << endl; 

  

    int arr2[] = {1, 2, 3, 4}; 

    int n2 = sizeof(arr2)/sizeof(arr2[0]); 

    cout << "The minimum element is " << findMin(arr2, 0, n2-1) << endl; 

  

    int arr3[] = {1}; 

    int n3 = sizeof(arr3)/sizeof(arr3[0]); 

    cout<<"The minimum element is "<<findMin(arr3, 0, n3-1)<<endl; 

  

    int arr4[] = {1, 2}; 

    int n4 = sizeof(arr4)/sizeof(arr4[0]); 

    cout<<"The minimum element is "<<findMin(arr4, 0, n4-1)<<endl; 

  

    int arr5[] = {2, 1}; 

    int n5 = sizeof(arr5)/sizeof(arr5[0]); 

    cout<<"The minimum element is "<<findMin(arr5, 0, n5-1)<<endl; 

  

    int arr6[] = {5, 6, 7, 1, 2, 3, 4}; 

    int n6 = sizeof(arr6)/sizeof(arr6[0]); 

    cout<<"The minimum element is "<<findMin(arr6, 0, n6-1)<<endl; 

  

    int arr7[] = {1, 2, 3, 4, 5, 6, 7}; 

    int n7 = sizeof(arr7)/sizeof(arr7[0]); 

    cout << "The minimum element is " << findMin(arr7, 0, n7-1) << endl; 

  

    int arr8[] = {2, 3, 4, 5, 6, 7, 8, 1}; 

    int n8 = sizeof(arr8)/sizeof(arr8[0]); 

    cout << "The minimum element is " << findMin(arr8, 0, n8-1) << endl; 

  

    int arr9[] = {3, 4, 5, 1, 2}; 

    int n9 = sizeof(arr9)/sizeof(arr9[0]); 

    cout << "The minimum element is " << findMin(arr9, 0, n9-1) << endl; 

  

    return 0; 

  

  
// Это код, предоставленный rathbhupendra

С

// C программа для поиска минимального элемента в отсортированном и повернутом массиве
#include <stdio.h>

  

int findMin(int arr[], int low, int high)

{

    // Это условие необходимо для обработки случая, когда массив не

    // вращается на всех

    if (high < low)  return arr[0];

  

    // Если остался только один элемент

    if (high == low) return arr[low];

  

    // Найти середину

    int mid = low + (high - low)/2; / * (низкий + высокий) / 2; * /

  

    // Проверяем, является ли элемент (mid + 1) минимальным. Рассмотреть возможность

    // такие случаи, как {3, 4, 5, 1, 2}

    if (mid < high && arr[mid+1] < arr[mid])

       return arr[mid+1];

  

    // Проверяем, является ли середина минимальным элементом

    if (mid > low && arr[mid] < arr[mid - 1])

       return arr[mid];

  

    // Решаем, нужно ли нам идти в левую или правую половину

    if (arr[high] > arr[mid])

       return findMin(arr, low, mid-1);

    return findMin(arr, mid+1, high);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr1[] =  {5, 6, 1, 2, 3, 4};

    int n1 = sizeof(arr1)/sizeof(arr1[0]);

    printf("The minimum element is %d\n", findMin(arr1, 0, n1-1));

  

    int arr2[] =  {1, 2, 3, 4};

    int n2 = sizeof(arr2)/sizeof(arr2[0]);

    printf("The minimum element is %d\n", findMin(arr2, 0, n2-1));

  

    int arr3[] =  {1};

    int n3 = sizeof(arr3)/sizeof(arr3[0]);

    printf("The minimum element is %d\n", findMin(arr3, 0, n3-1));

  

    int arr4[] =  {1, 2};

    int n4 = sizeof(arr4)/sizeof(arr4[0]);

    printf("The minimum element is %d\n", findMin(arr4, 0, n4-1));

  

    int arr5[] =  {2, 1};

    int n5 = sizeof(arr5)/sizeof(arr5[0]);

    printf("The minimum element is %d\n", findMin(arr5, 0, n5-1));

  

    int arr6[] =  {5, 6, 7, 1, 2, 3, 4};

    int n6 = sizeof(arr6)/sizeof(arr6[0]);

    printf("The minimum element is %d\n", findMin(arr6, 0, n6-1));

  

    int arr7[] =  {1, 2, 3, 4, 5, 6, 7};

    int n7 = sizeof(arr7)/sizeof(arr7[0]);

    printf("The minimum element is %d\n", findMin(arr7, 0, n7-1));

  

    int arr8[] =  {2, 3, 4, 5, 6, 7, 8, 1};

    int n8 = sizeof(arr8)/sizeof(arr8[0]);

    printf("The minimum element is %d\n", findMin(arr8, 0, n8-1));

  

    int arr9[] =  {3, 4, 5, 1, 2};

    int n9 = sizeof(arr9)/sizeof(arr9[0]);

    printf("The minimum element is %d\n", findMin(arr9, 0, n9-1));

  

    return 0;

}

Джава

// Java программа для поиска минимального элемента в отсортированном и повернутом массиве

import java.util.*;

import java.lang.*;

import java.io.*;

  

class Minimum

{

    static int findMin(int arr[], int low, int high)

    {

        // Это условие необходимо для обработки случая, когда массив

        // вообще не вращается

        if (high < low)  return arr[0];

  

        // Если остался только один элемент

        if (high == low) return arr[low];

  

        // Найти середину

        int mid = low + (high - low)/2; / * (низкий + высокий) / 2; * /

  

        // Проверяем, является ли элемент (mid + 1) минимальным. Рассмотреть возможность

        // такие случаи, как {3, 4, 5, 1, 2}

        if (mid < high && arr[mid+1] < arr[mid])

            return arr[mid+1];

  

        // Проверяем, является ли середина минимальным элементом

        if (mid > low && arr[mid] < arr[mid - 1])

            return arr[mid];

  

        // Решаем, нужно ли нам идти в левую или правую половину

        if (arr[high] > arr[mid])

            return findMin(arr, low, mid-1);

        return findMin(arr, mid+1, high);

    }

  

    // Программа для водителя

    public static void main (String[] args)

    {

        int arr1[] =  {5, 6, 1, 2, 3, 4};

        int n1 = arr1.length;

        System.out.println("The minimum element is "+ findMin(arr1, 0, n1-1));

  

        int arr2[] =  {1, 2, 3, 4};

        int n2 = arr2.length;

        System.out.println("The minimum element is "+ findMin(arr2, 0, n2-1));

  

        int arr3[] =  {1};

        int n3 = arr3.length;

        System.out.println("The minimum element is "+ findMin(arr3, 0, n3-1));

  

        int arr4[] =  {1, 2};

        int n4 = arr4.length;

        System.out.println("The minimum element is "+ findMin(arr4, 0, n4-1));

  

        int arr5[] =  {2, 1};

        int n5 = arr5.length;

        System.out.println("The minimum element is "+ findMin(arr5, 0, n5-1));

  

        int arr6[] =  {5, 6, 7, 1, 2, 3, 4};

        int n6 = arr6.length;

        System.out.println("The minimum element is "+ findMin(arr6, 0, n6-1));

  

        int arr7[] =  {1, 2, 3, 4, 5, 6, 7};

        int n7 = arr7.length;

        System.out.println("The minimum element is "+ findMin(arr7, 0, n7-1));

  

        int arr8[] =  {2, 3, 4, 5, 6, 7, 8, 1};

        int n8 = arr8.length;

        System.out.println("The minimum element is "+ findMin(arr8, 0, n8-1));

  

        int arr9[] =  {3, 4, 5, 1, 2};

        int n9 = arr9.length;

        System.out.println("The minimum element is "+ findMin(arr9, 0, n9-1));

    }

}

питон

# Python программа для поиска минимального элемента
# в отсортированном и повернутом массиве

  

def findMin(arr, low, high):

    # Это условие необходимо для обработки случая, когда массив не

    # повернуто на всех

    if high < low:

        return arr[0]

  

    # Если остался только один элемент

    if high == low:

        return arr[low]

  

    # Найти середину

    mid = int((low + high)/2)

  

    # Проверьте, является ли элемент (середина + 1) минимальным элементом. Рассмотреть возможность

    # случаи как [3, 4, 5, 1, 2]

    if mid < high and arr[mid+1] < arr[mid]:

        return arr[mid+1]

  

    # Проверьте, является ли середина минимальным элементом

    if mid > low and arr[mid] < arr[mid - 1]:

        return arr[mid]

  

    # Решите, нужно ли нам идти в левую или правую половину

    if arr[high] > arr[mid]:

        return findMin(arr, low, mid-1)

    return findMin(arr, mid+1, high)

  
# Драйверная программа для проверки вышеуказанных функций

arr1 = [5, 6, 1, 2, 3, 4]

n1 = len(arr1)

print("The minimum element is " + str(findMin(arr1, 0, n1-1)))

  

arr2 = [1, 2, 3, 4]

n2 = len(arr2)

print("The minimum element is " + str(findMin(arr2, 0, n2-1)))

  

arr3 = [1]

n3 = len(arr3)

print("The minimum element is " + str(findMin(arr3, 0, n3-1)))

  

arr4 = [1, 2]

n4 = len(arr4)

print("The minimum element is " + str(findMin(arr4, 0, n4-1)))

  

arr5 = [2, 1]

n5 = len(arr5)

print("The minimum element is " + str(findMin(arr5, 0, n5-1)))

  

arr6 = [5, 6, 7, 1, 2, 3, 4]

n6 = len(arr6)

print("The minimum element is " + str(findMin(arr6, 0, n6-1)))

  

arr7 = [1, 2, 3, 4, 5, 6, 7]

n7 = len(arr7)

print("The minimum element is " + str(findMin(arr7, 0, n7-1)))

  

arr8 = [2, 3, 4, 5, 6, 7, 8, 1]

n8 = len(arr8)

print("The minimum element is " + str(findMin(arr8, 0, n8-1)))

  

arr9 = [3, 4, 5, 1, 2]

n9 = len(arr9)

print("The minimum element is " + str(findMin(arr9, 0, n9-1)))

  
# Этот код предоставлен Pratik Chhajer

C #

// C # программа для поиска минимального элемента
// в отсортированном и повернутом массиве

using System;

  

class Minimum {

  

    static int findMin(int[] arr, int low, int high)

    {

        // Это условие необходимо обработать

        // случай, когда массив

        // вообще не вращается

        if (high < low)

            return arr[0];

  

        // Если остался только один элемент

        if (high == low)

            return arr[low];

  

        // Найти середину

        // (низкий + высокий) / 2

        int mid = low + (high - low) / 2; 

  

        // Проверяем, является ли элемент (mid + 1) минимальным. Рассмотреть возможность

        // такие случаи, как {3, 4, 5, 1, 2}

        if (mid < high && arr[mid + 1] < arr[mid])

            return arr[mid + 1];

  

        // Проверяем, является ли середина минимальным элементом

        if (mid > low && arr[mid] < arr[mid - 1])

            return arr[mid];

  

        // Решаем, нужно ли нам идти в

        // левая половина или правая половина

        if (arr[high] > arr[mid])

            return findMin(arr, low, mid - 1);

        return findMin(arr, mid + 1, high);

    }

  

    // Программа для водителя

    public static void Main()

    {

        int[] arr1 = { 5, 6, 1, 2, 3, 4 };

        int n1 = arr1.Length;

        Console.WriteLine("The minimum element is "

                           findMin(arr1, 0, n1 - 1));

  

        int[] arr2 = { 1, 2, 3, 4 };

        int n2 = arr2.Length;

        Console.WriteLine("The minimum element is "

                           findMin(arr2, 0, n2 - 1));

  

        int[] arr3 = { 1 };

        int n3 = arr3.Length;

        Console.WriteLine("The minimum element is "

                           findMin(arr3, 0, n3 - 1));

  

        int[] arr4 = { 1, 2 };

        int n4 = arr4.Length;

        Console.WriteLine("The minimum element is "

                           findMin(arr4, 0, n4 - 1));

  

        int[] arr5 = { 2, 1 };

        int n5 = arr5.Length;

        Console.WriteLine("The minimum element is "

                           findMin(arr5, 0, n5 - 1));

  

        int[] arr6 = { 5, 6, 7, 1, 2, 3, 4 };

        int n6 = arr6.Length;

        Console.WriteLine("The minimum element is "

                           findMin(arr6, 0, n1 - 1));

  

        int[] arr7 = { 1, 2, 3, 4, 5, 6, 7 };

        int n7 = arr7.Length;

        Console.WriteLine("The minimum element is " +

                           findMin(arr7, 0, n7 - 1));

  

        int[] arr8 = { 2, 3, 4, 5, 6, 7, 8, 1 };

        int n8 = arr8.Length;

        Console.WriteLine("The minimum element is "

                           findMin(arr8, 0, n8 - 1));

  

        int[] arr9 = { 3, 4, 5, 1, 2 };

        int n9 = arr9.Length;

        Console.WriteLine("The minimum element is "

                           findMin(arr9, 0, n9 - 1));

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для поиска минимума
// элемент в отсортированном и
// вращаемый массив

  

function findMin($arr, $low

                 $high)

{

    // Это условие необходимо

    // для обработки случая, когда

    // массив вообще не вращается

    if ($high < $low) return $arr[0];

  

    // Если есть только

    // остался один элемент

    if ($high == $low) return $arr[$low];

  

    // Найти середину

    $mid = $low + ($high - $low) / 2; / * ($ low + $ high) / 2; * /

  

    // Проверяем, если элемент (mid + 1)

    // минимальный элемент.

    // Рассмотрим случаи как

    // (3, 4, 5, 1, 2)

    if ($mid < $high && 

        $arr[$mid + 1] < $arr[$mid])

    return $arr[$mid + 1];

  

    // Проверяем, находится ли середина

    // минимальный элемент

    if ($mid > $low && 

        $arr[$mid] < $arr[$mid - 1])

    return $arr[$mid];

  

    // Решаем, нужно ли нам

    // перейти в левую половину или

    // правая половина

    if ($arr[$high] > $arr[$mid])

    return findMin($arr, $low

                   $mid - 1);

    return findMin($arr

                   $mid + 1, $high);

}

  
// Код драйвера

$arr1 = array(5, 6, 1, 2, 3, 4);

$n1 = sizeof($arr1);

echo "The minimum element is "

    findMin($arr1, 0, $n1 - 1) . "\n";

  

$arr2 = array(1, 2, 3, 4);

$n2 = sizeof($arr2);

echo "The minimum element is "

    findMin($arr2, 0, $n2 - 1) . "\n";

  

$arr3 = array(1);

$n3 = sizeof($arr3);

echo "The minimum element is "

    findMin($arr3, 0, $n3 - 1) . "\n";

  

$arr4 = array(1, 2);

$n4 = sizeof($arr4);

echo "The minimum element is "

    findMin($arr4, 0, $n4 - 1) . "\n";

  

$arr5 = array(2, 1);

$n5 = sizeof($arr5);

echo "The minimum element is "

    findMin($arr5, 0, $n5 - 1) . "\n";

  

$arr6 = array(5, 6, 7, 1, 2, 3, 4);

$n6 = sizeof($arr6);

echo "The minimum element is "

    findMin($arr6, 0, $n6 - 1) . "\n";

  

$arr7 = array(1, 2, 3, 4, 5, 6, 7);

$n7 = sizeof($arr7);

echo "The minimum element is "

    findMin($arr7, 0, $n7 - 1) . "\n";

  

$arr8 = array(2, 3, 4, 5, 6, 7, 8, 1);

$n8 = sizeof($arr8);

echo "The minimum element is "

    findMin($arr8, 0, $n8 - 1) . "\n";

  

$arr9 = array(3, 4, 5, 1, 2);

$n9 = sizeof($arr9);

echo "The minimum element is " .

    findMin($arr9, 0, $n9 - 1) . "\n";

  
// Этот код предоставлен ChitraNayal
?>


Выход:

The minimum element is 1
The minimum element is 1
The minimum element is 1
The minimum element is 1
The minimum element is 1
The minimum element is 1
The minimum element is 1
The minimum element is 1
The minimum element is 1

Как обрабатывать дубликаты?
Оказалось, что дубликаты не могут быть обработаны за O (Logn) время во всех случаях. Спасибо Amit Jain за вклад. Особые случаи, которые вызывают проблемы, такие как {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} и {2, 2, 2, 0, 2, 2, 2, 2 , 2, 2, 2, 2}. Невозможно перейти к левой или правой половине, выполнив постоянное число сравнений в середине. Таким образом, проблема с повторением может быть решена в O (n) худшем случае.

Эта статья предоставлена Абхай Рати . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти минимальный элемент в отсортированном и повернутом массиве

0.00 (0%) 0 votes