wake-up-neo.com

Suchen in einem sortierten und gedrehten Array

Bei der Vorbereitung auf ein Tech-Interview bin ich auf diese interessante Frage gestoßen:

Sie haben ein Array erhalten, das sortiert und dann gedreht wird.

beispiel

Lassen Sie arr = [1,2,3,4,5] den sortieren und dann zweimal nach rechts drehen, um zu geben

[4,5,1,2,3]

Wie kann man nun am besten in diesem sortierten + gedrehten Array suchen?

Man kann das Array aufheben und dann eine binäre Suche durchführen. Es ist jedoch nicht besser als eine lineare Suche im Eingabefeld, da beide im ungünstigsten Fall O (N) sind.

Bitte geben Sie einige Hinweise. Ich habe viel nach speziellen Algorithmen dafür gegoogelt, aber keine gefunden.

Ich verstehe C und C++

59
Jones

Dies kann in O(logN) mit einer leicht modifizierten binären Suche durchgeführt werden.

Die interessante Eigenschaft eines sortierten + gedrehten Arrays ist, dass, wenn Sie es in zwei Hälften teilen, mindestens eine der beiden Hälften immer sortiert wird.

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

scheinbar wird das rechte Unterfeld nicht sortiert, während das linke Unterfeld sortiert wird.

Wenn der Drehpunkt in der Mitte liegt, werden sowohl die linken als auch die rechten Sub-Arrays sortiert. 

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

Inmuss jedoch auf jeden Fall eine Hälfte (Sub-Array) sortiert werden.

Wir können leicht feststellen, welche Hälfte sortiert ist, indem wir Start- und Endelement jeder Hälfte vergleichen.

Wenn wir herausgefunden haben, welche Hälfte sortiert ist, können wir sehen, ob der Schlüssel in diesem halb einfachen Vergleich mit den Extremen vorhanden ist.

Wenn der Schlüssel in dieser Hälfte vorhanden ist, rufen wir die Funktion in dieser Hälfte rekursiv auf 
sonst nennen wir unsere Suche rekursiv auf der anderen Hälfte.

Wir verwerfen in jedem Aufruf eine Hälfte des Arrays, wodurch dieser Algorithmus O(logN) wird.

Pseudo-Code:

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

Der Schlüssel hier ist, dass immer ein Subarray sortiert wird, mit dem wir eine Hälfte des Arrays verwerfen können.

136
codaddict

Sie können 2 binäre Suchvorgänge durchführen: Zuerst müssen Sie den Index i suchen, beispielsweise arr[i] > arr[i+1]

Offensichtlich sind (arr\[1], arr[2], ..., arr[i]) und (arr[i+1], arr[i+2], ..., arr[n]) beide sortierte Arrays.

Wenn arr[1] <= x <= arr[i], führt man die binäre Suche im ersten Array durch, ansonsten im zweiten.

Die Komplexität O(logN)

BEARBEITEN: der Code .

14
Max

Die ausgewählte Antwort weist einen Fehler auf, wenn das Array doppelte Elemente enthält. Zum Beispiel suchen wir nach arr = {2,3,2,2,2} und 3. Das Programm in der ausgewählten Antwort gibt -1 statt 1 zurück. 

Diese Interviewfrage wird ausführlich im Buch "Cracking the Coding Interview" behandelt. Der Zustand doppelter Elemente wird in diesem Buch speziell besprochen. Da der Op in Kommentar gesagt hat, dass Array-Elemente alles sein können, gebe ich meine Lösung als Pseudocode im Folgenden:

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
11
ChuanRocks

Mein erster Versuch wäre, mit Hilfe der binären Suche die Anzahl der angewendeten Rotationen zu finden - dies kann durch Auffinden des Index n mit a [n]> a [n + 1] unter Verwendung des üblichen binären Suchmechanismus .. durchgeführt werden reguläre binäre Suche, während alle Indizes pro gefundener Schicht gedreht werden.

8
RomanK
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;
}
4
Akki Javed

Wenn Sie wissen, dass das Array nach rechts gedreht wurde, können Sie einfach eine binäre Suche durchführen, die nach rechts verschoben ist. Das ist O (lg N)

Damit meine ich, das linke Limit auf s und das Recht auf (s-1) mod N zu initialisieren und eine binäre Suche zwischen diesen durchzuführen.

Wenn Sie nicht wissen, um wie viel das Array gedreht wurde, können Sie mithilfe einer binären Suche (O (lg N)) bestimmen, wie groß die Rotation ist. Führen Sie dann eine verschobene binäre Suche aus, O (lg N), a Gesamtsumme von O (lg N) noch.

Antwort für den oben genannten Beitrag "Diese Interviewfrage wird im Buch" Cracking the Coding Interview "ausführlich erörtert. Der Zustand doppelter Elemente wird in diesem Buch speziell erörtert gebe meine Lösung als Pseudo-Code in:

Ihre Lösung ist O(n) !! (Die letzte if-Bedingung, bei der Sie beide Hälften des Arrays auf eine einzelne Bedingung überprüfen, macht sie zu einem Sol mit linearer Zeitkomplexität.)

Es ist besser, eine lineare Suche durchzuführen, als in einem Labyrinth aus Fehlern und Segmentierungsfehlern während einer Codierrunde stecken zu bleiben.

Ich glaube nicht, dass es eine bessere Lösung gibt als O(n) für eine Suche in einem rotierten sortierten Array (mit Duplikaten)

2
NIKUNJ BHARTIA

Wenn Sie wissen, wie weit (weit) gedreht wurde, können Sie immer noch eine binäre Suche durchführen. 

Der Trick ist, dass Sie zwei Ebenen von Indizes erhalten: Sie machen die bs. in einem virtuellen 0..n-1-Bereich und lösen Sie sie dann, wenn Sie tatsächlich nach einem Wert suchen. 

2
Henk Holterman

sie müssen das Array nicht zuerst drehen, Sie können die binäre Suche für das gedrehte Array verwenden (mit einigen Änderungen).

angenommen, N ist die Nummer, nach der Sie suchen:

lesen Sie die erste Zahl (Arr [Start]) und die Zahl in der Mitte des Arrays (Arr [Ende]):

  • if arr [start]> arr [end] -> Die erste Hälfte ist nicht sortiert, aber die zweite Hälfte ist sortiert:

    • wenn arr [Ende]> N -> Die Nummer ist im Index: (Mitte + N - Arr [Ende])

    • wenn N die Suche im ersten Teil des Arrays wiederholen (siehe Ende, um die Mitte der ersten Hälfte des Arrays usw. zu sein).

(dasselbe, wenn der erste Teil sortiert ist, der zweite jedoch nicht)

2
SivGo
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;
}
1
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;
}

}
1
RockSolid

Zuerst müssen Sie die Verschiebungskonstante k finden. Dies kann in der Zeit O(lgN) erfolgen. Mit der Konstantenverschiebung k können Sie das gewünschte Element mithilfe von Einer binären Suche mit der Konstanten k leicht finden. Die erweiterte binäre Suche dauert auch O(lgN) Die Gesamtlaufzeit beträgt O (lgN + lgN) = O(lgN) 

Um die konstante Verschiebung zu finden, k. Sie müssen nur nach dem Mindestwert im Array suchen. Der Index des Mindestwerts des Arrays gibt die konstante Verschiebung an. Betrachten Sie das sortierte Array [1,2,3,4,5]. 

Die möglichen Schichten sind: 
 [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 

Um einen Algorithmus in der Zeit O(lgN) auszuführen, müssen Sie immer nach Wegen suchen, um das Problem zu halbieren. Danach ist der Rest der Implementierungsdetails einfach

Unten ist der Code in C++ für den Algorithmus

// 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; 
}
 Hoffe, das hilft! =) 
 Bald Chee Loong, 
 Universität von Toronto 
1
Chee Loong Soon

Dieser Code in C++ sollte für alle Fälle funktionieren. Obwohl er mit Duplikaten funktioniert, lassen Sie mich wissen, ob in diesem Code ein Fehler vorliegt.

#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;
}
0
Siddhant

Mein einfacher Code: -

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

Zeitkomplexität O (log (N)).

0
HeadAndTail

Wenn Sie bei einem gedrehten Array mit Duplikaten das erste Vorkommen eines Elements suchen müssen, können Sie die folgende Prozedur verwenden (Java-Code):

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

}

Dies ist eine Verbesserung des oben genannten Verfahrens von Codaddict. Beachten Sie die zusätzliche if-Bedingung wie folgt:

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

Frage: Suche im rotierten sortierten Array

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;
    }
}
0
Soudipta Dutta

Hier ist eine einfache (zeitliche, räumliche) effiziente nichtrekursive O (log n) -Python-Lösung, die das ursprüngliche Array nicht ändert. Schneidet das gedrehte Array in zwei Hälften herunter, bis ich nur noch zwei zu überprüfende Indizes habe und die richtige Antwort zurückgibt, wenn ein Index übereinstimmt.

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
0
Leon

Ein anderer Ansatz, der mit wiederholten Werten arbeiten würde, besteht darin, die Rotation zu finden und dann bei jedem Zugriff auf das Array eine reguläre binäre Suche durchzuführen. 

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

Versuchen Sie diese Lösung 

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