LeetCode之Search in Rotated Sorted Array II

【题目】

Search in Rotated Sorted Array II

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

【分析】

相比上一道题点击打开链接，这道题允许重复元素出现，则上一道题中的A[start] <= A[mid] 条件就不能确定[start mid]区间为递增有序序列了。

比如：｛1，3，1，1，1，1｝

如果A[start] <= A[mid] 条件就不能确定[start mid]区间为递增有序序列，我们就把该条件分成两个字条件：

A[start] < A[mid] 则 [start mid]区间为递增有序序列

A[start] = A[mid] 则[start mid]区间不能确定，那就start++，往下一步看看即可。

【代码】

/*********************************
*   日期：2014-01-15
*   作者：SJF0115
*   题号: Search in Rotated Sorted Array II
*   来源：http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include 
  
   
#include 
   
     using namespace std; class Solution { public: //二分查找 bool search(int A[], int n, int target) { int start = 0,end = n-1; int mid; while(start <= end){ mid = (start + end) / 2; if(A[mid] == target){ return true; } //中间元素大于最左边元素则左部分为有序数组 else if(A[mid] > A[start]){ //目标位于左部分 if(target >= A[start] && target <= A[mid]){ end = mid - 1; } //目标位于右部分 else{ start = mid + 1; } } //中间元素小于最左边元素则右部分为有序数组 else if(A[mid] < A[start]){ //目标位于右部分 if(target <= A[end] && target >= A[mid]){ start = mid + 1; } //目标位于左部分 else{ end = mid - 1; } } //中间元素等于最左边元素则无法区分有序部分 else{ start++; } } return false; } }; int main() { int result; Solution solution; int A[] = {4,5,1,2,3}; result = solution.search(A,5,4); printf("Result:%d\n",result); return 0; } 
   
  

【测试】

[1,1,3,1], 3

[3,1], 1