LeetCode 搜索旋转排序数组【二分查找】

短命女 2022-09-12 06:54 152阅读 0赞

# 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 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
    输出：4

示例 2：

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

示例 3：

输入：nums = [1], target = 0
    输出：-1

提示：

1 <= nums.length <= 5000
    -10^4 <= nums[i] <= 10^4
    nums 中的每个值都 独一无二
    题目数据保证 nums 在预先未知的某个下标上进行了旋转
    -10^4 <= target <= 10^4

# 2 代码 #

public int search(int[] nums, int target) { 
            if (nums.length == 0) { 
                return -1;
            }
            if (nums.length == 1) { 
                return nums[0] == target ? 0 : -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[0]) { 
                    //左边是升序
                    if (target >= nums[0] && target < nums[mid]) { 
                        right = mid - 1;
                    } else { 
                        left = mid + 1;
                    }
    
                } else { 
                    //右边是升序
                    if (target > nums[mid] && target <= nums[nums.length - 1]) { 
                        left = mid + 1;
                    } else { 
                        right = mid - 1;
                    }
    
                }
            }
            return -1;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e8bcf09917c64149a7a9c8d1bd57d7e5.png