本文主要是介绍leetcode 刷题之路 35 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.
这道题是 Search in Rotated Sorted Array升级版本，要求从一个旋转过得有序数组查找一个给定数字，但是这道题给出的数字中存在重复的数字。
这里我把两道题目统一，给出一个适配两道题的答案，程序的逻辑在注释中说明。
accepted answer:
class Solution {
public:bool search(int A[], int n, int target) {int mid;int begin=0,end=n-1;while(begin<=end){mid=(begin+end)/2;if(A[mid]==target)return true;if(A[mid]>A[begin]) //两个升序序列的话，mid必然位于第一个序列，因为第二个序列的数都小于等于begin{if(target>=A[begin]&&target<A[mid])end=mid-1;elsebegin=mid+1;}else if(A[mid]<A[begin])//两个升序序列的话，mid必然位于第二个序列，因为第一个序列的数都大于等于begin{if(target>A[mid]&&target<=A[end])begin=mid+1;elseend=mid-1;}else //相等的时候，说明begin位置数字有重复，重复元素位于第一个序列的前面，或者第二个序列后面{if(A[mid]==A[end]) //此条件下，不能判断mid位于哪个位置的重复元素中，只能移动最小的位置{++begin;--end;}elsebegin=mid+1; //此条件下，重复数字都位于第一个序列，故begin和mid之间所有数字都相同}}return false;}
};
这篇关于leetcode 刷题之路 35 Search in Rotated Sorted Array II （旋转排序数组查找终极版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
