정렬 및 회전 배열 검색

정렬 및 회전 배열 검색

인터뷰를 준비하던 중 우연히 다음과 같은 흥미로운 질문을 받았습니다.

정렬된 다음 회전하는 배열이 제공되었습니다.

예를 들어 다음과 같습니다.

• let let 렛츠고arr = [1,2,3,4,5]되어 있습니다.
• 오른쪽으로 두 번 돌려주세요.

이 정렬된 회전식 어레이에서 검색하려면 어떻게 해야 할까요?

어레이의 회전을 해제하고 바이너리 검색을 실행할 수 있습니다.그러나 둘 다 최악의 경우 O(N)이기 때문에 이는 입력 배열에서 선형 검색을 수행하는 것과 다를 바 없습니다.

몇 가지 조언을 해 주세요.나는 이것에 대한 특별한 알고리즘들을 많이 검색해봤지만 아무것도 찾을 수 없었다.

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

여기서 중요한 것은 1개의 서브 어레이는 항상 정렬되며, 이를 사용하여 어레이의 절반을 폐기할 수 있다는 것입니다.

어레이에 중복된 요소가 있는 경우 승인된 답변에 오류가 있습니다.를 들어, 「」라고 하는 것은,arr = {2,3,2,2,2}3시 30분그러면 승인된 답변의 프로그램은 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[high])    
        // 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

검색을 할 수 첫 번째로 수 있습니다. 먼저 인덱스를 찾습니다.iarr[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: 코드.

첫 번째 시도는 적용된 회전수를 바이너리 검색을 사용하여 찾는 것입니다.이것은 일반적인 바이너리 검색 메커니즘을 사용하여 인덱스 n을 찾는 것으로 실행할 수 있습니다.그런 다음 발견된 교대조당 모든 인덱스를 회전시키면서 정기적으로 이진 검색을 수행합니다.

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

어레이가 오른쪽으로 회전한 경우 오른쪽으로 이동된 이진 검색을 수행할 수 있습니다.O(lg N)입니다.

즉, 왼쪽 한계를 s로, 오른쪽 한계를 (s-1) mod N으로 초기화하여 올바른 영역에서 작업하도록 약간 주의를 기울이면서 이들 사이에서 바이너리 검색을 수행합니다.

어레이가 어느 정도 회전했는지 모를 경우 O(lg N)의 바이너리 검색을 사용하여 회전 크기를 판별한 다음 O(lg N)의 합계인 O(lg N)의 시프트 바이너리 검색을 실행할 수 있습니다.

위의 게시물에 대한 회신: "이 인터뷰 질문은 '코딩 인터뷰의 크래킹'이라는 책에서 자세히 설명되어 있습니다.그 책에서는 중복 원소의 상태에 대해 특별히 논하고 있다.op에서는 어레이 요소가 무엇이든 될 수 있다고 코멘트하고 있기 때문에, 이하의 의사 코드로 솔루션을 제공하고 있습니다.」

솔루션은 O(n)!! (마지막으로 어레이의 양쪽 반쪽에서1개의 조건을 체크하면 시간이 복잡해집니다)

코딩 라운드에서 버그와 분할 오류의 미로에 갇히는 것보다는 선형 검색을 하는 것이 좋습니다.

O(n)보다 더 좋은 솔루션은 회전 정렬된 배열(복제 포함)에서 검색하는 데 없다고 생각합니다.

회전(원거리) 방법을 알고 있으면 이진 검색을 계속 수행할 수 있습니다.

여기서 중요한 것은 두 가지 수준의 인덱스를 얻는 것입니다.가상 0..n-1 범위에서 b.s를 실행하고 실제 값을 조회할 때 회전하지 않는 것입니다.

어레이를 먼저 회전할 필요는 없습니다.회전된 배열에서 바이너리 검색을 사용할 수 있습니다(일부 수정).

N을 검색하는 번호로 합니다.

첫 번째 숫자(arr[start])와 배열 중간에 있는 숫자(arr[end])를 읽습니다.

• arr [ start ]> arr [ end ] -- > 전반부가 정렬되지 않고 후반부가 정렬된 경우:

  • arr [ end ]> N -- > 번호가 인덱스에 있는 경우: (중간 + N - arr [ end ])

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

이게 도움이 됐으면 좋겠네요!=)곧 Chee Loong,토론토 대학교

중복이 있는 회전 배열의 경우 요소가 처음 발생하는 경우 다음 절차(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);
    }       

}

이것은 위의 공동 중독자의 절차를 개선한 것입니다.다음과 같은 추가 if 조건에 주의하십시오.

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

다음은 원래 어레이를 수정하지 않는 단순(시간, 공간) 효율적인 비재귀 O(log n) python 솔루션입니다.체크할 인덱스가 2개밖에 없을 때까지 회전 배열을 반으로 자르고 한 인덱스가 일치하면 정답을 반환합니다.

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], 대상 = 0 출력:

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(log(n)에서 해결 방법을 찾을 수 있습니다.많은 사람들이 이를 보여 주었기 때문에, 수정된 버전의 이진 검색을 사용하여 대상 요소를 찾을 수 있습니다.

• 다만, 어레이에 중복이 있는 경우는, O(log(n)로 타겟 요소를 찾을 수 없다고 생각합니다.다음은 O(log(n)가 불가능하다고 생각하는 이유를 보여 줍니다.다음의 2개의 어레이에 대해 생각해 봅시다.

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

모든 점들은 숫자 2로 채워져 있다.양쪽 어레이가 정렬되어 회전하고 있는 것을 알 수 있습니다.바이너리 검색을 검토하려면 반복할 때마다 검색 도메인을 절반으로 줄여야 합니다. 이렇게 하면 O(log(n)가 나옵니다.숫자 3을 찾고 있다고 가정해 봅시다.첫 번째 케이스에서는 어레이의 오른쪽에 숨김을 알 수 있으며 두 번째 케이스에서는 어레이의 두 번째에 숨김을 알 수 있습니다.이 단계에서 어레이에 대해 알고 있는 것은 다음과 같습니다.

• 왼쪽 = 0
• 오른쪽 = 길이 - 1;
• 중간 = 왼쪽 + (오른쪽 - 왼쪽) / 2;
• arr[mid] = 2;
• arr[왼쪽] = 2;
• arr[right] = 2;
• 대상 = 3;

이게 우리가 가진 모든 정보입니다.어레이의 절반을 제외하기로 결정하는 것만으로는 충분하지 않다는 것을 분명히 알 수 있습니다.그 결과, 유일한 방법은 선형 검색을 하는 것입니다.O(n) 시간을 최적화할 수 없다는 것이 아니라 O(log(n) 시간을 최적화할 수 없다는 것입니다.

미드, 미드1 등 바이너리 검색을 싫어하는 점이 있어 항상 바이너리 스트라이드/점프 검색을 사용합니다.

회전 어레이에서 사용하는 방법두 번 사용합니다(일단 shift를 찾은 후 .at()를 사용하여 shifted 인덱스 -> 원래 인덱스를 찾습니다).

또는 첫 번째 요소를 비교해 보십시오. 첫 번째 요소보다 작으면 끝 부분에 가까워야 합니다.

끝에서 뒤로 점프 검색을 수행하고 피벗 티에가 발견되면 중지합니다.

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

Swift 솔루션 100% 동작 테스트 완료

 func searchInArray(A:[Int],key:Int)->Int{
        for i in 0..<A.count{
            if key == A[i] {
                print(i)
                return i
            }
        }
        print(-1)
        return -1
    }

언급URL : https://stackoverflow.com/questions/4773807/searching-in-a-sorted-and-rotated-array