Suchen in einem sortierten und gedrehten Array

Während ich mich auf ein Interview vorbereitete, stieß ich auf diese interessante Frage:

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

Zum Beispiel:

• Lassen Sie arr = [1,2,3,4,5], die sortiert ist
• Drehen Sie es zweimal nach rechts, 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. Dies ist jedoch nicht besser als eine lineare Suche im Eingabearray, da beide O (N) im ungünstigsten Fall sind.

Bitte geben Sie einige Hinweise. Ich habe viel über spezielle Algorithmen gegoogelt, konnte aber keine finden.

Ich verstehe C und C ++.

Dies kann O(logN)mithilfe einer leicht modifizierten binären Suche erfolgen.

Die interessante Eigenschaft eines sortierten + gedrehten Arrays ist, dass beim Teilen in zwei Hälften immer mindestens eine der beiden Hälften 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

Wie es scheint, wird das rechte Subarray nicht sortiert, während das linke Subarray sortiert wird.

Wenn die Mitte der Drehpunkt ist, werden sowohl die linken als auch die rechten Unterarrays sortiert.

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

In jedem Fall muss jedoch eine Hälfte (Sub-Array) sortiert werden .

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

Sobald wir herausgefunden haben, welche Hälfte sortiert ist, können wir sehen, ob der Schlüssel in dieser Hälfte vorhanden ist - einfacher Vergleich mit den Extremen.

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

Wir verwerfen bei jedem Aufruf die Hälfte des Arrays, wodurch dieser Algorithmus erstellt wird O(logN).

Pseudocode:

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 Sub-Array sortiert wird, mit dem wir eine Hälfte des Arrays verwerfen können.

Die akzeptierte Antwort weist einen Fehler auf, wenn das Array doppelte Elemente enthält. Zum Beispiel arr = {2,3,2,2,2}und 3 ist das, wonach wir suchen. Dann gibt das Programm in der akzeptierten Antwort -1 anstelle von 1 zurück.

Diese Interviewfrage wird im Buch 'Cracking the Coding Interview' ausführlich besprochen. Der Zustand doppelter Elemente wird in diesem Buch speziell erörtert. Da die Operation in einem Kommentar sagte, dass Array-Elemente alles sein können, gebe ich meine Lösung unten als Pseudocode an:

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

Sie können zwei binäre Suchen durchführen: Zuerst müssen Sie den Index iso finden, dass arr[i] > arr[i+1].

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

Wenn arr[1] <= x <= arr[i]ja, führen Sie eine binäre Suche im ersten Array durch, andernfalls im zweiten.

Die Komplexität O(logN)

EDIT: der Code .

Mein erster Versuch wäre, mithilfe der binären Suche die Anzahl der angewendeten Umdrehungen zu ermitteln. Dies kann durch Ermitteln des Index n mit a [n]> a [n + 1] unter Verwendung des üblichen binären Suchmechanismus erfolgen. Führen Sie dann eine regelmäßige binäre Suche durch, während Sie alle Indizes pro gefundener Schicht drehen.

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

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. Dies ist O (lg N)

Damit meine ich, initialisiere die linke Grenze auf s und die rechte auf (s-1) mod N und führe eine binäre Suche zwischen diesen durch, wobei du ein wenig darauf achtest, im richtigen Bereich zu arbeiten.

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

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

Der Trick besteht darin, dass Sie zwei Ebenen von Indizes erhalten: Sie führen die bs in einem virtuellen 0..n-1-Bereich aus und drehen sie dann wieder auf, wenn Sie tatsächlich nach einem Wert suchen.

Antwort auf den oben genannten Beitrag "Diese Interviewfrage wird im Buch 'Cracking the Coding Interview' ausführlich besprochen. Der Zustand doppelter Elemente wird in diesem Buch speziell besprochen. Da die Operation im Kommentar sagte, dass Array-Elemente alles sein können, habe ich Ich gebe meine Lösung als Pseudocode unten an: "

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

Ich bin besser dran, eine lineare Suche durchzuführen, als während einer Codierungsrunde in einem Labyrinth von Fehlern und Segmentierungsfehlern stecken zu bleiben.

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

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

Sei N die Nummer, nach der Sie suchen:

Lesen Sie die erste Nummer (arr [start]) und die Nummer in der Mitte des Arrays (arr [end]):

• wenn arr [start]> arr [end] -> wird die erste Hälfte nicht sortiert, aber die zweite Hälfte wird sortiert:

  • wenn arr [Ende]> N -> ist die Zahl im Index: (Mitte + N - arr [Ende])

  • Wenn N, wiederholen Sie die Suche im ersten Teil des Arrays (siehe Ende als Mitte der ersten Hälfte des Arrays usw.)

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

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

Zuerst müssen Sie die Verschiebungskonstante k finden. Dies kann in O (lgN) Zeit erfolgen. Aus der konstanten Verschiebung k können Sie das gesuchte Element mithilfe einer binären Suche mit der Konstanten k leicht finden. Die erweiterte binäre Suche benötigt auch O (lgN) Zeit. 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 Minimalwerts des Arrays gibt die konstante Verschiebung an. Betrachten Sie das sortierte Array [1,2,3,4,5].

Die möglichen Verschiebungen 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 O (lgN) -Zeit ausführen zu können, müssen immer Wege gefunden werden, um das Problem durch die Hälfte zu teilen. Sobald dies geschehen ist, 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 

Wenn für ein gedrehtes Array mit Duplikaten das erste Vorkommen eines Elements gefunden werden muss, kann das folgende Verfahren angewendet werden (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 beschriebenen Verfahrens von codaddict. Beachten Sie die zusätzliche if-Bedingung wie folgt:

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

Hier ist eine einfache (Zeit, Raum) effiziente nicht rekursive O (log n) Python-Lösung, die das ursprüngliche Array nicht ändert. Zerhackt das gedrehte Array in zwei Hälften, bis ich nur noch zwei Indizes zu überprüfen habe, und gibt die richtige Antwort zurück, 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

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

Dieser Code in C ++ sollte in allen Fällen funktionieren. Obwohl er mit Duplikaten funktioniert, lassen Sie mich bitte wissen, ob dieser Code einen Fehler enthält.

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

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

Eingabe: nums = [4,5,6,7,0,1,2], Ziel = 0 Ausgabe: 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);
        }
    }

}

Hier sind meine zwei Cent:

• Wenn das Array nicht nicht Duplikate enthalten, kann man die Lösung in O (log (n)) finden. Wie viele Leute gezeigt haben, kann eine optimierte Version der binären Suche verwendet werden, um das Zielelement zu finden.

• Wenn das Array jedoch Duplikate enthält, gibt es meines Erachtens keine Möglichkeit, das Zielelement in O (log (n)) zu finden. Hier ist ein Beispiel, das zeigt, warum ich denke, dass O (log (n)) nicht möglich ist. Betrachten Sie die beiden folgenden Arrays:

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

Alle Punkte sind mit der Nummer 2 gefüllt. Sie können sehen, dass beide Arrays sortiert und gedreht sind. Wenn man die binäre Suche in Betracht ziehen möchte, muss man die Suchdomäne bei jeder Iteration um die Hälfte reduzieren - so erhalten wir O (log (n)). Nehmen wir an, wir suchen nach der Nummer 3. Im ersten Fall sehen wir, dass sie sich auf der rechten Seite des Arrays versteckt, und im zweiten Fall auf der zweiten Seite des Arrays. Folgendes wissen wir zu diesem Zeitpunkt über das Array:

• links = 0
• rechts = Länge - 1;
• Mitte = links + (rechts - links) / 2;
• arr [mid] = 2;
• arr [links] = 2;
• arr [rechts] = 2;
• Ziel = 3;

Dies sind alle Informationen, die wir haben. Wir können deutlich sehen, dass es nicht ausreicht, eine Entscheidung zum Ausschluss einer Hälfte des Arrays zu treffen. Infolgedessen besteht die einzige Möglichkeit in der linearen Suche. Ich sage nicht, dass wir diese O (n) -Zeit nicht optimieren können, ich sage nur, dass wir O (log (n)) nicht tun können.

Es gibt etwas, das ich an der binären Suche wegen Mitte, Mitte 1 usw. nicht mag, deshalb verwende ich immer die binäre Schritt- / Sprung-Suche

Wie verwende ich es auf einem gedrehten Array? zweimal verwenden (einmal Shift finden und dann mit .at () den verschobenen Index finden -> Originalindex)

Oder vergleichen Sie das erste Element. Wenn es kleiner als das erste Element ist, muss es sich dem Ende nähern

Führen Sie eine Rückwärtssprungsuche vom Ende aus durch und halten Sie an, wenn ein Drehpunkt gefunden wird

Wenn es> Startelement ist, mache einfach eine normale Sprungsuche :)

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

Ein anderer Ansatz, der mit wiederholten Werten funktionieren würde, besteht darin, die Rotation zu finden und dann eine regelmäßige binäre Suche durchzuführen, bei der die Rotation angewendet wird, wenn wir auf das Array zugreifen.

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

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

Frage: Suche in gedrehtem sortiertem 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;
    }
}