（LeetCode）Java 求解搜索旋转排序数组

╰+攻爆jí腚メ 2022-10-24 13:26 79阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、代码
     *  三、总结
     *  四、补充

## 一、题目 ##

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， \[0,1,2,4,5,6,7\] 经旋转后可能变为 \[4,5,6,7,0,1,2\] ）。

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

--------------------

解析：  
该题可以使用常规的左右指针，左右夹逼找到target。

也可以采用二分搜索的思路：

*  由于该数组是旋转后的数组，所以首先需要确定 中间值 mid 在左部还是右部，然后再调整左右边界
 *  如果在左部例如：\[3,4,5,6,7,1,2\]
 *  如果在右部例如：\[5,6,7,1,2,3,4\]

## 二、代码 ##

class Solution { 
        public int search(int[] nums, int target) { 
            if(target>nums[nums.length-1] && target < nums[0]){ 
                return -1;
            }
            int left = 0;
            int right = nums.length-1;
            while(left<=right){ 
                int mid = (left+right)/2;
                if(nums[mid]==target){ 
                    return mid;
                }
                //中间值在左边
                if(nums[mid]>=nums[left]){ 
                    //left 到 mid 是递增的
                    if(target>=nums[left] && target<=nums[mid]){ 
                        right = mid-1;
                    }else{ 
                        left = mid +1;
                    }
                }else{ 
                    //mid 到 right 是递增的
                    if(target>=nums[mid] && target<=nums[right]){ 
                        left = mid +1;
                    }else{ 
                        right = mid -1;
                    }
                }
            }
            return -1;
        }
    }

## 三、总结 ##

本题中关键在于需要根据 中间值，分段考虑来确定左右的边界

同时注意等于号别忘加上，将等于号归于大于或小于中的情况

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 1]

## 四、补充 ##

刷过 [在排序数组中查找元素的第一个和最后一个位置][Link 1]

之后，发现对于二分查找，打算以后都使用 while(left<right)，排除元素找符合的目标的方法，  
所以对代码进行了改写，大体思路没有变，只是将 `nums[mid]==target`，归于了左半部。也就是此时的两段区间是 \[left,mid\]，\[mid+1,right\]，所以对应的mid 是向下取整

class Solution { 
        public int search(int[] nums, int target) { 
            if(target>nums[nums.length-1] && target < nums[0]){ 
                return -1;
            }
            int left = 0;
            int right = nums.length-1;
            while(left<right){ 
                int mid = left + (right-left)/2;
               
                //中间值在左边
                if(nums[mid]>=nums[left]){ 
                    if(target>=nums[left] && target<=nums[mid]){ 
                        right = mid;
                    }else{ 
                        left = mid +1;
                    }
                }else{ 
                    if(target>nums[mid] && target<=nums[right]){ 
                        left = mid +1;
                    }else{ 
                        right = mid;
                    }
                }
            }
    
            return nums[left]==target ? left:-1;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221024/548e7683305644e4995d99dff9cbad41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 1]: /images/20221024/5e0ac71ccdde4e56aef70663a0fd16f5.png
[Link 1]: https://blog.csdn.net/nanhuaibeian/article/details/113447870