LintCode (63) Search in Rotated Sorted Array

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

本来想取个巧，套下模板，然后只是在mid=beg的时候beg+1进位一下就好。。。不成想。。。其实里面那层二分的时候也有重复的状况，所以干脆回归经典吧。。。其实最开始之所以错是生套beg=mid, end=mid,但是因为有rotate，中间那个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

class Solution { /** * param A : an integer ratated sorted array and duplicates are allowed * param target : an integer to be search * return : a boolean */ public: bool search(vector<int> &A, int target) { // write your code here if (A.empty()) return false; int beg=0; int end=A.size()-1; while(beg+1<end){ int mid=beg+(end-beg)/2; if (A[mid]==target) return true; if (A[mid]>A[beg]){ if (A[mid]>=target && target>=A[beg]){ end=mid-1; } else{ beg=mid+1; } } else if (A[mid]<A[beg]){ if (A[mid]<=target && target<=A[end]){ beg=mid+1; } else{ end=mid-1; } } else{ beg++; } } return (A[beg]==target || A[end]==target); } };