LintCode (62) Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Have you met this question in a real interview? 

Yes

Example

For [4, 5, 1, 2, 3] and target=1, return 2.

For [4, 5, 1, 2, 3] and target=0, return -1.

Challenge

O(logN) time

画一下图就好，比较一下rotate以后，会发现，只有中间transient的位置才需要特别处理，否则还是正常的bsearch. 二分法的话，就是区别左旋区间还是右旋区间， 左旋的话就是mid>beg, 右旋的话就是mid<beg

然后还要再分一次，就是递增递减区间还是位于transient 区间

      /                           /

    /                           /

  /                                    /    

/                                    /

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

class Solution { /** * 二分法， 只是分的时候只用bsearch找target在 * [beg,end]的区间内，另一种情形用else来cover * 子情况为左旋右旋， 左旋和右旋各包括一种sorted * 和非sorted得情况 * param A : an integer ratated sorted array * param target : an integer to be searched * return : an integer */ public: int search(vector<int> &A, int target) { // write your code here if (A.empty()) return -1; int beg=0; int end=A.size()-1; while(beg+1<end){ int mid=beg+(end-beg)/2; if (A[mid]>A[beg]){ if (A[mid]>=target && A[beg]<=target) end=mid; else beg=mid; } else{ if (A[mid]<=target && A[end]>=target) beg=mid; else end=mid; } } if (A[beg]==target) return beg; if (A[end]==target) return end; return -1; } };