leetcode 题解：Search in Rotated Sorted Array II （旋转已排序数组查找2）
题目：
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.
说明：
1）和1比只是有重复的数字，整体仍采用二分查找
2）方法二 ：
实现：
一、我的实现：
1 class Solution { 2 public: 3 bool search(int A[], int n, int target) { 4 if(n==0||n==1&&A[0]!=target) return false; 5 if(A[0]==target) return true; 6 int i=1; 7 while(A[i-1]<=A[i]) i++; 8 9 bool pre=binary_search(A,0,i,target); 10 bool pos=binary_search(A,i,n-i,target); 11 return pre==false?pos:pre; 12 } 13 private: 14 bool binary_search(int *B,int lo,int len,int goal) 15 { 16 int low=lo; 17 int high=lo+len-1; 18 while(low<=high) 19 { 20 int middle=(low+high)/2; 21 if(goal==B[middle])//找到，返回index 22 return true; 23 else if(B[middle]<goal)//在右边 24 low=middle+1; 25 else//在左边 26 high=middle-1; 27 } 28 return false;//没有，返回-1 29 } 30 };
二、网上开源实现：
1 class Solution { 2 public: 3 bool search(int A[], int n, int target) { 4 int low=0; 5 int high=n-1; 6 while(low<=high) 7 { 8 const int middle=(low+high)/2; 9 if(A[middle]==target) return true; 10 if(A[low]<A[middle]) 11 { 12 if(A[low]<=target&&target<A[middle]) 13 high=middle-1; 14 else 15 low=middle+1; 16 } 17 else if(A[low]>A[middle]) 18 { 19 if(A[middle]<target&&target<=A[high]) 20 low=middle+1; 21 else 22 high=middle-1; 23 } 24 else 25 low++; 26 } 27 return false; 28 } 29 };