341
[LeetCode]81.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
* 來源：https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
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
最後更新：2017-04-03 12:54:31