Leetcode之Search in Rotated Sorted Array 问题
问题描述:
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
问题来源:Search in Rotated Sorted Array (详细地址:https://leetcode.com/problems/search-in-rotated-sorted-array/description/)
思路分析:这道题和Rotate Array 好像有点点相像,但是这道题是要在Rotate Array的基础之上找到指定的数字,所以这道题稍微要复杂些。题目明显说了这是递增的数组旋转后所得,所以肯定也是二分查找喽,但是该怎么下手寻找呢?我们不妨按照下面的步骤开始(当然还有其他的方法,我在这只是介绍一种思路):
第一步:我们根据二分查找找到整个数组中最小数的索引minIndex,在这和Search for a Range 一样,我们采用的是"合并式"的二分查找,比较的是nums[mid]和nums[high],然后变动指针,尤其是条件nums[mid] <= nums[high]满足的时候,不能是high = mid - 1,这样有可能一步就跳过了最小值;
第二步:找到最小值的索引之后,我们就需要确认下一步目标target在哪边了,因为这样我们就能进行下一步的二分查找工作了。我们比较nums[length - 1]和target的大小情况,如果前者大于等于后者,那么新一轮搜索位于后半部分,start = minIndex,end = length - 1;相反的,start = 0, end = minIndex;
第三步:正宗的二分查找,也没啥好说的了。
代码:
主体部分:
查找最小索引部分: