Поиск в отсортированном и повернутом массиве

Ответ 1

Это можно сделать в O(logN), используя слегка измененный двоичный поиск.

Интересным свойством сортированного + повернутого массива является то, что когда вы делите его на две половины, по крайней мере одна из двух половинок всегда будет сортироваться.

Let input array arr = [4,5,6,7,8,9,1,2,3]
number of elements  = 9
mid index = (0+8)/2 = 4

[4,5,6,7,8,9,1,2,3]
         ^
 left   mid  right

как кажется, правый суб-массив не сортируется, а оставшийся под-массив сортируется.

Если середина оказывается точкой поворота, они будут отсортированы как слева, так и справа.

[6,7,8,9,1,2,3,4,5]
         ^

Но в в любом случае одна половина (подматрица) должна быть отсортирована.

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

Как только мы найдем, какая половина будет отсортирована, мы увидим, присутствует ли ключ в этом полупростом сравнении с крайностями.

Если ключ присутствует в этой половине, мы рекурсивно вызываем функцию на этой половине иначе мы рекурсивно будем называть наш поиск на другой половине.

Мы отбрасываем одну половину массива в каждом вызове, который делает этот алгоритм O(logN).

Псевдокод:

function search( arr[], key, low, high)

        mid = (low + high) / 2

        // key not present
        if(low > high)
                return -1

        // key found
        if(arr[mid] == key)
                return mid

        // if left half is sorted.
        if(arr[low] <= arr[mid]) {

                // if key is present in left half.
                if (arr[low] <= key && arr[mid] >= key) 
                        return search(arr,key,low,mid-1)

                // if key is not present in left hald..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if righ half is sorted. 
        else    
                // if key is present in right half.
                if(arr[mid] <= key && arr[high] >= key) 
                        return search(arr,key,mid+1,high)

                // if key is not present in right half..search in left half.
                else
                        return search(arr,key,low,mid-1)
                end-if
        end-if  

end-function

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

Ответ 2

Вы можете выполнить 2 бинарных поиска: сначала найдите индекс i, чтобы arr[i] > arr[i+1].

По-видимому, (arr\[1], arr[2], ..., arr[i]) и (arr[i+1], arr[i+2], ..., arr[n]) - это отсортированные массивы.

Тогда, если arr[1] <= x <= arr[i], вы выполняете двоичный поиск в первом массиве, иначе на втором.

Сложность O(logN)

EDIT: код.

Ответ 3

Выбранный ответ имеет ошибку, если в массиве есть повторяющиеся элементы. Например, arr = {2,3,2,2,2} и 3 - это то, что мы ищем. Тогда программа в выбранном ответе вернет -1 вместо 1.

Этот вопрос об интервью подробно обсуждается в книге "Крекинг для кодирования интервью". Условие дублирующих элементов специально обсуждается в этой книге. Поскольку op говорит в комментарии, что элементы массива могут быть чем угодно, я даю свое решение как псевдокод ниже:

function search( arr[], key, low, high)

    if(low > high)
        return -1

    mid = (low + high) / 2

    if(arr[mid] == key)
        return mid

    // if the left half is sorted.
    if(arr[low] < arr[mid]) {

        // if key is in the left half
        if (arr[low] <= key && key <= arr[mid]) 
            // search the left half
            return search(arr,key,low,mid-1)
        else
            // search the right half                 
            return search(arr,key,mid+1,high)
        end-if

    // if the right half is sorted. 
    else if(arr[mid] < arr[low])    
        // if the key is in the right half.
        if(arr[mid] <= key && arr[high] >= key) 
            return search(arr,key,mid+1,high)
        else
            return search(arr,key,low,mid-1)
        end-if

    else if(arr[mid] == arr[low])

        if(arr[mid] != arr[high])
            // Then elements in left half must be identical. 
            // Because if not, then it impossible to have either arr[mid] < arr[high] or arr[mid] > arr[high]
            // Then we only need to search the right half.
            return search(arr, mid+1, high, key)
        else 
            // arr[low] = arr[mid] = arr[high], we have to search both halves.
            result = search(arr, low, mid-1, key)
            if(result == -1)
                return search(arr, mid+1, high, key)
            else
                return result
   end-if
end-function

Ответ 4

Моя первая попытка состояла в том, чтобы найти с помощью двоичного поиска число применений вращения - это можно сделать, найдя индекс n, где a [n] > a [n + 1], используя обычный механизм бинарного поиска. Затем выполните регулярный двоичный поиск при вращении всех индексов за сдвиг.

Ответ 5

Если вы знаете, что массив повернут s вправо, вы можете просто выполнить двоичный поиск, сдвинутый вправо. Это O (lg N)

Под этим я подразумеваю инициализацию левого предела до s и право на (s-1) mod N и выполняю двоичный поиск между ними, немного заботясь о работе в правильной области.

Если вы не знаете, сколько массива было повернуто, вы можете определить, насколько большой оборот использует двоичный поиск, то есть O (lg N), а затем сдвинутый двоичный поиск, O (lg N), общее количество O (lg N) все еще.

Ответ 6

Если вы знаете, как (далеко) он был повернут, вы все равно можете выполнить двоичный поиск.

Фокус в том, что вы получаете два уровня индексов: вы делаете b.s. в виртуальном диапазоне 0..n-1, а затем не вращать их при фактическом поиске значения.

Ответ 7

вам не нужно сначала вращать массив, вы можете использовать двоичный поиск по повернутому массиву (с некоторыми изменениями)

предположим, что N - это номер, который вы ищете:

прочитайте первое число (arr [start]) и число в середине массива (arr [конец]):

• если arr [start] > arr [end] → первая половина не сортируется, а вторая половина сортируется:

  • если arr [end] > N → номер в индексе: (middle + N - arr [end])

  • если N повторяет поиск в первой части массива (см. конец, чтобы быть серединой первой половины массива и т.д.)

(то же самое, если первая часть сортируется, а вторая - нет)

Ответ 8

int rotated_binary_search(int A[], int N, int key) {
  int L = 0;
  int R = N - 1;

  while (L <= R) {
    // Avoid overflow, same as M=(L+R)/2
    int M = L + ((R - L) / 2);
    if (A[M] == key) return M;

    // the bottom half is sorted
    if (A[L] <= A[M]) {
      if (A[L] <= key && key < A[M])
        R = M - 1;
      else
        L = M + 1;
    }
    // the upper half is sorted
    else {
      if (A[M] < key && key <= A[R])
        L = M + 1;
      else
        R = M - 1;
    }
  }
  return -1;
}

Ответ 9

Ваше решение - O (n)!! (Последнее, если условие, в котором вы проверяете обе половины массива для одного условия, делает его зоной линейной временной сложности)

Мне лучше делать линейный поиск, чем застревать в лабиринте ошибок и ошибок сегментации во время раунда кодирования.

Я не думаю, что есть лучшее решение, чем O (n) для поиска во вращающемся отсортированном массиве (с дубликатами)

Ответ 10

short mod_binary_search( int m, int *arr, short start, short end)
{

 if(start <= end)
 {
    short mid = (start+end)/2;

    if( m == arr[mid])
        return mid;
    else
    {
        //First half is sorted
        if(arr[start] <= arr[mid])
        {
            if(m < arr[mid] && m >= arr[start])
                return mod_binary_search( m, arr, start, mid-1);
            return mod_binary_search( m, arr, mid+1, end);
        }

        //Second half is sorted
        else
        {
            if(m > arr[mid] && m < arr[start])
                return mod_binary_search( m, arr, mid+1, end);
            return mod_binary_search( m, arr, start, mid-1);
        }
    }
 }
 return -1;
}

Ответ 11

Во-первых, вам нужно найти постоянную сдвига k. Это можно сделать в O (lgN). Из постоянного сдвига k вы можете легко найти элемент, который вы ищете, используя двоичный поиск с константой k. Расширенный бинарный поиск также принимает время O (lgN)  Общее время выполнения: O (lgN + lgN) = O (lgN)

Чтобы найти постоянный сдвиг, k. Вам просто нужно искать минимальное значение в массиве. Индекс минимального значения массива указывает вам постоянный сдвиг. Рассмотрим отсортированный массив [1,2,3,4,5].

The possible shifts are:
    [1,2,3,4,5] // k = 0
    [5,1,2,3,4] // k = 1
    [4,5,1,2,3] // k = 2
    [3,4,5,1,2] // k = 3
    [2,3,4,5,1] // k = 4
    [1,2,3,4,5] // k = 5%5 = 0 

Для выполнения любого алгоритма в O (lgN) время ключ всегда должен найти способы разделить проблему наполовину. После этого остальная часть деталей реализации проста

Ниже приведен код в С++ для алгоритма

// This implementation takes O(logN) time
// This function returns the amount of shift of the sorted array, which is
// equivalent to the index of the minimum element of the shifted sorted array. 
#include <vector> 
#include <iostream> 
using namespace std; 

int binarySearchFindK(vector<int>& nums, int begin, int end)
{
    int mid = ((end + begin)/2); 
    // Base cases
    if((mid > begin && nums[mid] < nums[mid-1]) || (mid == begin && nums[mid] <= nums[end]))     
        return mid; 
    // General case 
    if (nums[mid] > nums[end]) 
    {
        begin = mid+1; 
        return binarySearchFindK(nums, begin, end); 
    }
    else
    {
        end = mid -1; 
        return binarySearchFindK(nums, begin, end); 
    }   
}  
int getPivot(vector<int>& nums)
{
    if( nums.size() == 0) return -1; 
    int result = binarySearchFindK(nums, 0, nums.size()-1); 
    return result; 
}

// Once you execute the above, you will know the shift k, 
// you can easily search for the element you need implementing the bottom 

int binarySearchSearch(vector<int>& nums, int begin, int end, int target, int pivot)
{
    if (begin > end) return -1; 
    int mid = (begin+end)/2;
    int n = nums.size();  
    if (n <= 0) return -1; 

    while(begin <= end)
    {
        mid = (begin+end)/2; 
        int midFix = (mid+pivot) % n; 
        if(nums[midFix] == target) 
        {
            return midFix; 
        }
        else if (nums[midFix] < target)
        {
            begin = mid+1; 
        }
        else
        {
            end = mid - 1; 
        }
    }
    return -1; 
}
int search(vector<int>& nums, int target) {
    int pivot = getPivot(nums); 
    int begin = 0; 
    int end = nums.size() - 1; 
    int result = binarySearchSearch(nums, begin, end, target, pivot); 
    return result; 
}

Hope this helps!=)
Soon Chee Loong, 
University of Toronto 

Ответ 12

public class PivotedArray {

//56784321 first increasing than decreasing
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int [] data ={5,6,7,8,4,3,2,1,0,-1,-2};

    System.out.println(findNumber(data, 0, data.length-1,-2));

}

static int findNumber(int data[], int start, int end,int numberToFind){

    if(data[start] == numberToFind){
        return start;
    }

    if(data[end] == numberToFind){
        return end;
    }
    int mid = (start+end)/2;
    if(data[mid] == numberToFind){
        return mid;
    }
    int idx = -1;
    int midData = data[mid];
    if(numberToFind < midData){
        if(midData > data[mid+1]){
            idx=findNumber(data, mid+1, end, numberToFind);
        }else{
            idx =  findNumber(data, start, mid-1, numberToFind);
        }
    }

    if(numberToFind > midData){
        if(midData > data[mid+1]){
            idx =  findNumber(data, start, mid-1, numberToFind);

        }else{
            idx=findNumber(data, mid+1, end, numberToFind);
        }
    }
    return idx;
}

}

Ответ 13

Вот простое (время, пространство) эффективное нерекурсивное решение O (log n) python, которое не изменяет исходный массив. Отбрасывает повернутый массив пополам, пока у меня не будет только двух индексов для проверки и вернет правильный ответ, если один индекс соответствует.

def findInRotatedArray(array, num):

lo,hi = 0, len(array)-1
ix = None


while True:


    if hi - lo <= 1:#Im down to two indices to check by now
        if (array[hi] == num):  ix = hi
        elif (array[lo] == num): ix = lo
        else: ix = None
        break

    mid = lo + (hi - lo)/2
    print lo, mid, hi

    #If top half is sorted and number is in between
    if array[hi] >= array[mid] and num >= array[mid] and num <= array[hi]:
        lo = mid

    #If bottom half is sorted and number is in between
    elif array[mid] >= array[lo] and num >= array[lo] and num <= array[mid]:
        hi = mid


    #If top half is rotated I know I need to keep cutting the array down
    elif array[hi] <= array[mid]:
        lo = mid

    #If bottom half is rotated I know I need to keep cutting down
    elif array[mid] <= array[lo]:
        hi = mid

print "Index", ix

Ответ 14

Другим подходом, который будет работать с повторяющимися значениями, является поиск вращения, а затем регулярный двоичный поиск, применяющий поворот, когда мы обращаемся к массиву.

test = [3, 4, 5, 1, 2]
test1 = [2, 3, 2, 2, 2]

def find_rotated(col, num):
    pivot = find_pivot(col)
    return bin_search(col, 0, len(col), pivot, num)

def find_pivot(col):
    prev = col[-1]
    for n, curr in enumerate(col):
        if prev > curr:
            return n
        prev = curr
    raise Exception("Col does not seem like rotated array")

def rotate_index(col, pivot, position):
    return (pivot + position) % len(col)

def bin_search(col, low, high, pivot, num):
    if low > high:
        return None
    mid = (low + high) / 2
    rotated_mid = rotate_index(col, pivot, mid)
    val = col[rotated_mid]
    if (val == num):
        return rotated_mid
    elif (num > val):
        return bin_search(col, mid + 1, high, pivot, num)
    else:
        return bin_search(col, low, mid - 1,  pivot, num)

print(find_rotated(test, 2))
print(find_rotated(test, 4))
print(find_rotated(test1, 3))

Ответ 15

Попробуйте это решение

bool search(int *a, int length, int key)
{
int pivot( length / 2 ), lewy(0), prawy(length);
if (key > a[length - 1] || key < a[0]) return false;
while (lewy <= prawy){
    if (key == a[pivot]) return true;
    if (key > a[pivot]){
        lewy = pivot;
        pivot += (prawy - lewy) / 2 ? (prawy - lewy) / 2:1;}
    else{
        prawy = pivot;
        pivot -= (prawy - lewy) / 2 ? (prawy - lewy) / 2:1;}}
return false;
}

Ответ 16

Для вращающегося массива с дубликатами, если нужно найти первое вхождение элемента, можно использовать следующую процедуру (код Java):

public int mBinarySearch(int[] array, int low, int high, int key)
{
    if (low > high)
        return -1; //key not present

    int mid = (low + high)/2;

    if (array[mid] == key)
        if (mid > 0 && array[mid-1] != key)
            return mid;

    if (array[low] <= array[mid]) //left half is sorted
    {
        if (array[low] <= key && array[mid] >= key)
            return mBinarySearch(array, low, mid-1, key);
        else //search right half
            return mBinarySearch(array, mid+1, high, key);
    }
    else //right half is sorted
    {
        if (array[mid] <= key && array[high] >= key)
            return mBinarySearch(array, mid+1, high, key);
        else
            return mBinarySearch(array, low, mid-1, key);
    }       

}

Это усовершенствование процедуры codaddict выше. Обратите внимание на дополнительное условие if, как показано ниже:

if (mid > 0 && array[mid-1] != key)