《leetCode》：Search in Rotated Sorted Array II

本文主要是介绍《leetCode》：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可以看这篇博文

思路一：直接遍历

bool search(int* nums, int numsSize, int target) {if(nums==NULL||numsSize<1){return false;}for(int i=0;i<numsSize;i++){if(nums[i]==target){return true;}}return false;
}

虽然没有利用到旋转数组这一特性，时间复杂度为O(n),结果居然AC了。
AC结果如下：

思路二

上面这种思路并没有利用旋转数组这一特性，因此，这个思路将利用这个特性来减少时间复杂度。

bool search(int* nums, int numsSize, int target) {if(nums==NULL||numsSize<1){return false;}int begin=0;int end=numsSize-1;while(begin<=end){int mid=begin+(end-begin)/2;if(nums[mid]==target){return true;}//以下只比较nums[mid]与nums[end]的大小来控制end和begin的变化 if(nums[mid]<nums[end]){if(target>nums[mid]&&target<=nums[end])  begin=mid+1;else end=mid-1;}else if(nums[mid]>nums[end]){if(target>=nums[begin]&&target<nums[mid]) end=mid-1;else begin=mid+1;}else{end--;}}return false;
}