leetcode_60题目的变形
http://blog.sina.com.cn/s/blog_672f71fc0101pgf6.html
这次,array允许重复的。我适当改了下代码判断的情况。
仍然是o(logn)
class Solution { public: bool searchStep(int A[],int target,int left,int right) { if(left > right) return false; int mid = (left+right)/2; if(A[mid] == target) return true; else if(A[mid] > target) { if(A[right] > A[left]) return searchStep(A,target,left,mid-1); else return searchStep(A,target,left,mid-1) || searchStep(A,target,mid+1,right); } else { if(A[right] > A[left]) return searchStep(A,target,mid+1,right); else return searchStep(A,target,mid+1,right) || searchStep(A,target,left,mid-1); } } bool search(int A[], int n, int target) { int left = 0; int right = n-1; return searchStep(A,target,left,right); } };