您当前位置：首页 > php开源 > php教程 > [LeetCode] Search in Rotated Sorted Array

[LeetCode] Search in Rotated Sorted Array

来源：程序员人生发布时间：2015-09-06 08:31:45 阅读次数：2473次

Search in Rotated Sorted Array

Suppose a sorted array 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 ⑴.

You may assume no duplicate exists in the array.

解题思路：

题意为在旋转数组中找出目标数，与找最小数http://www.kangry.net/blog/?type=article&article_id=111是兄弟题目。类似于2分查找，分析1下即可。

数组元素：XX XX... XX XX... XX

数组下标：start middle end

如上所示，

1、若middle等于目标值，返回middle，若start等于目标值，则返回start，若end等于目标值，则返回end。

2、若middle大于目标值，并且start小于目标值，表示start到middle是顺序部份，且目标值肯定在start到middle部份（若存在的话），因此将end赋值为middle⑴

3、若middle小于目标值，并且end大于目标值，表示middle到end是顺序部份，且目标值肯定在middle到end部份（若存在的话），因此将start赋值为middle+1

4、若middle大于目标值，并且start大于目标值，这要分情况讨论。若start到middle不是顺序部份，表明target在start到middle之间（若存在的话），否则在middle到end之间

5、若middle小于目标值，且end小于目标值，分情况讨论，若middle到end不是顺序部份，则target在middle到end之间（若存在的话），否则在start到middle之间。

下面是代码：

class Solution { public: int search(vector<int>& nums, int target) { int start=0; int end=nums.size()⑴; int middle; while(start<=end){ middle=(start+end)/2; if(nums[middle]==target){ return middle; }else if(nums[start]==target){ return start; }else if(nums[end]==target){ return end; }else{ if(nums[middle]>target&&nums[start]<target){ end=middle⑴; }else if(nums[middle]<target&&nums[end]>target){ start=middle+1; }else if(nums[middle]>target&&nums[start]>target){ if(nums[middle]>nums[start]){ start=middle+1; }else{ end=middle⑴; } }else if(nums[middle]<target&&nums[end]<target){ if(nums[middle]<nums[end]){ end=middle⑴; }else{ start=middle+1; } } } } return ⑴; } };

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 session标签（会话实例）

下一篇 [置顶] 我的阿里实习生一面二面经验分享给大家

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点