leetcode 33 搜索旋转排序数组到处是细节的好题

水深无声 2023-06-17 03:55 1阅读 0赞

**这个题想了想就会做，只是细节真的能卡死人，找了好久的bug。甚至我怀疑我现在的代码可能还有错，只是没例子测出来。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = \[4,5,6,7,0,1,2\], target = 0  
输出: 4  
示例 2:

输入: nums = \[4,5,6,7,0,1,2\], target = 3  
输出: -1

思路：先二分找到旋转点，然后确定在旋转点左边查还是右边查，再二分查找目标。

需要注意的细节在代码中标注

class Solution {
        public int search(int[] nums, int target) {
            if(nums.length==0)return -1;//坑1
            if(nums.length==1){//坑2
                if(nums[0]==target)return 0;
                return -1;
            }
            int left=0;
            int right=nums.length-1;
            int index=nums.length-1;//旋转边界，坑3，初始化别的值是错的
            //确定旋转边界
            while(left<=right){
                int mid=(right-left)/2+left;
                if (mid==nums.length-1 || nums[mid] > nums[mid + 1]){
                //坑4，不加第一个条件会越界
                    index = mid+1;
                    break;
                }else if(nums[left]<=nums[mid]){
                //坑5，记得加=
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
            //确定在哪边二分查找
            if(target>=nums[0]){
            //坑6，记得加等于
                left=0;
                right=index-1;
            }else{
                left=index;
                right=nums.length-1;
            }
            //查找
            while(left<=right){
            //坑7，mid直接（right+left）/2可能超过int范围
                int mid=(right-left)/2+left;
                if(nums[mid]<target){
                    left=mid+1;
                }else if(nums[mid]>target){
                    right=mid-1;
                }else{
                    return mid;
                }
            }
            return -1;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191127125436747.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70