搜索旋转排序数组

ゞ浴缸里的玫瑰 2024-03-26 18:59 64阅读 0赞

[力扣][Link 1]

整数数组 `nums` 按升序排列，数组中的值 **互不相同** 。

在传递给函数之前，`nums` 在预先未知的某个下标 `k`（`0 <= k < nums.length`）上进行了 **旋转**，使数组变为 `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`（下标 **从 0 开始** 计数）。例如， `[0,1,2,4,5,6,7]` 在下标 `3` 处经旋转后可能变为 `[4,5,6,7,0,1,2]` 。

给你 **旋转后** 的数组 `nums` 和一个整数 `target` ，如果 `nums` 中存在这个目标值 `target` ，则返回它的下标，否则返回 `-1` 。

你必须设计一个时间复杂度为 `O(log n)` 的算法解决此问题。

二分法的使用：

二分法不局限于从有序数组中快速寻找某个数，而是具有二段性的数据进行划分。对于本题，二段性体现在元素是否大于nums\[0\]。如下图：

![ece8f6aa38064ce2975fad5183c030a7.png][]

所以思路是首先通过二分法，以nums\[0\]为划分标志对数组划分，然后找到起始点后，在根据target和起始点的大小判断是二分起始点右侧还是左侧。

class Solution {
        public int search(int[] nums, int target) {
            int n = nums.length;
            if(n == 0) return -1;
            if(n == 1 ) return nums[0] == target ? 0 : -1;
            int l = 0;
            int r = nums.length - 1;
    
            while(l < r){
                int mid = (l + r + 1) >> 1;
                if(nums[0] > nums[mid]){
                    r = mid - 1;
                }else{
                    l = mid ;
                }
            }
            //找到了升序的最后一个
            // System.out.print(l);
            if(nums[0] <= target){
                l  = 0;
            }
            else{
                r = nums.length - 1;
                l = l + 1;
            }
            //继续二分
            while(l < r){
                int mid = (l + r + 1) >> 1;
                if(nums[mid] > target){
                    r = mid - 1;
                }else{
                    l = mid;
                }
            }
            return nums[r] == target ? r:-1;
    
        }
    }

这里注意的是二分法的写法：

int mid = （l+ r + 1） >>1; r = mid - 1;

如果不加1，那么程序就会陷入死循环。。。。

[Link 1]: https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
[ece8f6aa38064ce2975fad5183c030a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/86fd07678ff74cb5b95646faa30426cf.png