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

Готовясь к собеседованию, я наткнулся на интересный вопрос:

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

Например:

• Пусть arr = [1,2,3,4,5], что отсортировано
• Дважды поверните его вправо, чтобы дать [4,5,1,2,3].

Теперь, как лучше всего искать в этом отсортированном + повернутом массиве?

Можно повернуть массив и затем выполнить двоичный поиск. Но это не лучше, чем выполнять линейный поиск во входном массиве, поскольку оба являются наихудшим значением O (N).

Пожалуйста, дайте несколько указателей. Я много искал в Google специальные алгоритмы для этого, но не нашел ни одного.

Я понимаю C и C ++.

Это можно сделать 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 half..search right half.
                else                 
                        return search(arr,key,mid+1,high)
                end-if

        // if right 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

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

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

Этот вопрос интервью подробно обсуждается в книге «Cracking the Coding Interview». В этой книге специально обсуждается состояние повторяющихся элементов. Поскольку оператор сказал в комментарии, что элементы массива могут быть любыми, я даю свое решение в виде псевдокода ниже:

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's 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

Вы можете выполнить 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)

РЕДАКТИРОВАТЬ: код .

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

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;
}

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

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

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

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

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

Ответ на вышеупомянутый пост «Этот вопрос интервью подробно обсуждается в книге« Cracking the Coding Interview ». В этой книге специально обсуждается состояние повторяющихся элементов. Поскольку оператор сказал в комментарии, что элементы массива могут быть любыми, я я даю свое решение в виде псевдокода ниже: "

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

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

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

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

Пусть N будет числом, которое вы ищете:

Прочтите первое число (arr [начало]) и число в середине массива (arr [end]):

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

  • если arr [конец]> N -> число находится в индексе: (средний + N - arr [конец])

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

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

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;
}

}

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;
}

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

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

Возможные сдвиги:
    [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), главное всегда находить способы разделить задачу пополам. После этого остальные детали реализации легко

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

// 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; 
}

Надеюсь, это поможет! =)
Скоро Чи Лунг, 
Университет Торонто 

Для повернутого массива с дубликатами, если нужно найти первое вхождение элемента, можно использовать следующую процедуру (код 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)

Вот простое (время, пространство) эффективное нерекурсивное решение 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

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

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;
}

Этот код на C ++ должен работать во всех случаях. Хотя он работает с дубликатами, сообщите мне, есть ли в этом коде ошибка.

#include "bits/stdc++.h"
using namespace std;
int searchOnRotated(vector<int> &arr, int low, int high, int k) {

    if(low > high)
        return -1;

    if(arr[low] <= arr[high]) {

        int p = lower_bound(arr.begin()+low, arr.begin()+high, k) - arr.begin();
        if(p == (low-high)+1)
            return -1;
        else
            return p; 
    }

    int mid = (low+high)/2;

    if(arr[low] <= arr[mid]) {

        if(k <= arr[mid] && k >= arr[low])
            return searchOnRotated(arr, low, mid, k);
        else
            return searchOnRotated(arr, mid+1, high, k);
    }
    else {

        if(k <= arr[high] && k >= arr[mid+1])
            return searchOnRotated(arr, mid+1, high, k);
        else
            return searchOnRotated(arr, low, mid, k);
    }
}
int main() {

    int n, k; cin >> n >> k;
    vector<int> arr(n);
    for(int i=0; i<n; i++) cin >> arr[i];
    int p = searchOnRotated(arr, 0, n-1, k);
    cout<<p<<"\n";
    return 0;
}

В Javascript

var search = function(nums, target,low,high) {
    low= (low || low === 0) ? low : 0;

    high= (high || high == 0) ? high : nums.length -1;

    if(low > high)
        return -1;

    let mid = Math.ceil((low + high) / 2);


    if(nums[mid] == target)
        return mid;

    if(nums[low] < nums[mid]) {
        // if key is in the left half
        if (nums[low] <= target && target <= nums[mid]) 
            // search the left half
            return search(nums,target,low,mid-1);
        else
            // search the right half                 
            return search(nums,target,mid+1,high);
    } else {
        // if the key is in the right half.
        if(nums[mid] <= target && nums[high] >= target) 
            return search(nums,target,mid+1,high)
        else
            return search(nums,target,low,mid-1)
    }
};

Вход: nums = [4,5,6,7,0,1,2], target = 0 Выход: 4

import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int arr[]=new int[n];
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        int min_index=0,max_index=n;

        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
            if(arr[i]>max){
                max=arr[i];
            max_index=i;
            }
            if(arr[i]<min){
                min=arr[i];
                min_index=i;
            }

        }

        int element=sc.nextInt();
        int index;
        if(element>arr[n-1]){
            index=Arrays.binarySearch(arr,0,max_index+1,element);
        }
        else {
             index=Arrays.binarySearch(arr,min_index,n,element);
        }
        if(index>=0){
            System.out.println(index);
        }
        else{
            System.out.println(-1);
        }
    }

}

Вот мои два цента:

• Если массив имеет не содержит дубликатов, можно найти решение в O (журнал (п)). Как показали многие люди, для поиска целевого элемента можно использовать измененную версию двоичного поиска.

• Однако, если массив содержит дубликаты, я думаю, что нет способа найти целевой элемент в O (log (n)). Вот пример, показывающий, почему я считаю, что O (log (n)) невозможно. Рассмотрим два массива ниже:

a = [2,.....................2...........3,6,2......2]
b = [2.........3,6,2........2......................2]

Все точки заполнены цифрой 2. Вы можете видеть, что оба массива отсортированы и повернуты. Если кто-то хочет рассмотреть двоичный поиск, он должен сокращать область поиска наполовину на каждой итерации - так мы получаем O (log (n)). Предположим, мы ищем число 3. В первом случае мы видим, что он прячется в правой части массива, а во втором случае он прячется во второй стороне массива. Вот что мы знаем о массиве на этом этапе:

• left = 0
• справа = длина - 1;
• mid = left + (справа - слева) / 2;
• arr [mid] = 2;
• arr [left] = 2;
• arr [right] = 2;
• target = 3;

Это вся информация, которая у нас есть. Мы ясно видим, что недостаточно принять решение об исключении одной половины массива. В результате единственный способ - это линейный поиск. Я не говорю, что мы не можем оптимизировать это время O (n), все, что я говорю, это то, что мы не можем сделать O (log (n)).

Есть что-то, что мне не нравится в двоичном поиске из-за mid, mid-1 и т.д., поэтому я всегда использую двоичный поиск с шагом / прыжком.

Как использовать его на вращающемся массиве? используйте дважды (один раз найдите сдвиг, а затем используйте .at (), чтобы найти сдвинутый индекс -> исходный индекс)

Или сравните первый элемент, если он меньше первого элемента, он должен быть ближе к концу

выполните поиск в обратном прыжке с конца, остановитесь, если найдена какая-либо точка поворота

если это> элемент start, просто выполните обычный поиск перехода :)

Реализовано с использованием C #

public class Solution {
        public int Search(int[] nums, int target) {
             if (nums.Length == 0) return -1;
                int low = 0;
                int high = nums.Length - 1;
                while (low <= high)
                {
                    int mid = (low + high) / 2;
                    if (nums[mid] == target) return mid;
                    if (nums[low] <= nums[mid]) // 3 4 5 6 0 1 2
                    {
                        if (target >= nums[low] && target <= nums[mid])
                            high = mid;
                        else
                            low = mid + 1;
                    }
                    else // 5 6 0 1 2 3 4
                    {
                        if (target >= nums[mid] && target <= nums[high])
                            low= mid;
                        else
                            high = mid - 1;
                    }
                }
                return -1;
        }
    }

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

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))

Мой простой код: -

public int search(int[] nums, int target) {
    int l = 0;
    int r = nums.length-1;
    while(l<=r){
        int mid = (l+r)>>1;
        if(nums[mid]==target){
            return mid;
        }
        if(nums[mid]> nums[r]){
            if(target > nums[mid] || nums[r]>= target)l = mid+1;
            else r = mid-1;
        }
        else{
            if(target <= nums[r] && target > nums[mid]) l = mid+1;
            else r = mid -1;
        }
    }
    return -1;
}

Сложность времени O (log (N)).

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

public class SearchingInARotatedSortedARRAY {
    public static void main(String[] args) {
        int[] a = { 4, 5, 6, 0, 1, 2, 3 };

        System.out.println(search1(a, 6));

    }

    private static int search1(int[] a, int target) {
        int start = 0;
        int last = a.length - 1;
        while (start + 1 < last) {
            int mid = start + (last - start) / 2;

            if (a[mid] == target)
                return mid;
            // if(a[start] < a[mid]) => Then this part of the array is not rotated
            if (a[start] < a[mid]) {
                if (a[start] <= target && target <= a[mid]) {
                    last = mid;
                } else {
                    start = mid;
                }
            }
            // this part of the array is rotated
            else {
                if (a[mid] <= target && target <= a[last]) {
                    start = mid;
                } else {
                    last = mid;
                }
            }
        } // while
        if (a[start] == target) {
            return start;
        }
        if (a[last] == target) {
            return last;
        }
        return -1;
    }
}