LeetCode--33.搜索旋转排序数组

解题思路：

        1.获取信息：

                一个数组是按升序排列的，并且没有重复的元素

                现在任意找出一个下标，将下标后面的元素及下标元素和前面的元素整体换个位置

                如：[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 

                要求：现在给出了一个旋转后的数组和一个整数，判断整数在不在这个数组中，如果在，就返回下标，如果不在，就返回-1

                限制条件：要求时间复杂度为O(log n)

                其他条件：（可以看一下题目下面的提示，这里就不一一列举）

        2.分析题目：

                看见这个时间复杂度，我就想到了二分查找法，那么该怎么用这个方法来解这道题呢？

                我想了两种方式，分别会在下面的方法中借着代码逐一讲解，在此之前，你可以自己先想一想

        3.示例查验：无

        4.尝试编写代码：

                （1）二分查找法 I 

                        思路：这道题如果想变得更简单的话，我想，那一定是知道了这个数组从哪里开始旋转的，那么我们可以找到这个旋转的点吗？

                        当然可以，我们取数组第一个元素作为参照，对整个数组进行二分查找

                        先初始化begin=0 , end=nums.size()-1

                        再循环，直到begin>=end

                        每次取中点mid，与数组第一个元素相比较，就会出现两种情况（默认它们不相等）

                        1.mid大于数组第一个元素

                                我们就取mid右边的区间继续循环，因为旋转点一定在右边的区间内

                        2.mid小于数组第一个元素

                                我们就取mid左边的区间继续循环，因为旋转点一定在左边的区间内

                        当循环完后，此时begin就是旋转点

                        那么下面就只需要确定在begin左边还是右边的区间取目标值了，那么怎么确定呢？

                        只需要比较数组第一个元素和目标值的大小即可，无非就两种情况（默认它们不相等）

                        1.数组第一个元素大于目标值，说明目标值在begin的右区间

                        2.数组第一个元素小于目标值，说明目标值在begin的左区间

                        接下来只需要常规的二分法查找目标值即可

以下是完整代码

class Solution {
public:int search(vector<int>& nums, int target) {int num=nums[0];//取数组第一个元素int size=nums.size()-1;//取数组的大小if(target==nums[size]||target==nums[0])return target==nums[0]?0:size;//如果队首或队尾是目标值就返回答案int begin=0,end=size;//要开始二分咯，这里是查找旋转点while(begin<end){int mid=(begin+end)/2;if(nums[mid]==target)return mid;if(num<nums[mid])begin=mid+1;else end=mid;}//此时begin就是旋转点了if(nums[begin]==target)return begin;//如果旋转点就是目标值，就返回答案if(begin==0||begin==size){//特殊情况：如果旋转点在队首或队尾，那么相当于数组是一个升序数组，没有进行旋转，就直接进行常规的二分查找法int newbegin=0,newend=size;while(newbegin<newend){int mid=(newbegin+newend)/2;if(nums[mid]==target)return mid;else if(nums[mid]>target)newend=mid;else newbegin=mid+1;}if(nums[newbegin]==target)return newbegin;return -1;}//以下是旋转点不在队首或队尾的情况if(nums[begin]>target)return -1;//如果目标值小于转折点对应的那个元素（该元素是数组的最小值）else if(nums[begin]<target){//如果目标值大于转折点对应的那个元素if(target==num)return 0;if(target>num){begin--; int newbegin=0,newend=begin;while(newbegin<newend){int mid=(newbegin+newend)/2;if(nums[mid]==target)return mid;else if(nums[mid]>target)newend=mid;else newbegin=mid+1;}if(nums[newbegin]==target)return newbegin;}else{int newbegin=begin,newend=size;while(newbegin<newend){int mid=(newbegin+newend)/2;if(nums[mid]==target)return mid;else if(nums[mid]>target)newend=mid;else newbegin=mid+1;}if(nums[newbegin]==target)return newbegin;}}return -1;}
};

                (2)二分查找法II

                思路：我们可以不可以不用找出旋转点直接使用二分法来做这道题呢？

                当然可以，我们直接使用二分查找法，取到了一个中点对吧

                那么这个中点将这个数组一分为二成了两个区间，我们知道，其中一个区间一定是升序排列，另一个区间就不一定是了

                那么我们可以根据目标值的大小来确定它是在哪个区间

                如果实在那个升序的区间，就可以使用二分查找法来直接查找到结果了

                如果不再那个升序的区间，那么此时这个区间

                我们可以把它看成是一个新的数组，并且这个数组是不是也是有一个旋转点，

                这么一看，此时就又回到了原点，就可以重复上述操作，直到找到结果

class Solution {
public:int search(vector<int>& nums, int target) {int size=nums.size();//数组的大小int l=0,r=size-1;//要开始二分查找法了while(l<r){int mid=(l+r)/2;if(nums[mid]==target)return mid;if(nums[0]<=nums[mid]){if(target>=nums[0]&&target<=nums[mid])r=mid;else{l=mid+1;}}else{if(target<=nums[size-1]&&target>=nums[mid])l=mid+1;else{r=mid-1;}}}return nums[l]==target?l:-1;}
};

以上就是本次题解的全部内容了

做一道题，不要只看题解，要自己再动手写一下，才会真正地得心应手，知道吗？

纸上得来终觉浅，绝知此事要躬行