LeetCode_二分搜索_中等_33.搜索旋转排序数组

╰半夏微凉° 2023-10-06 18:07 56阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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) 的解决方案**。

**示例 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  
\-104 <= nums\[i\] <= 104  
nums 中的每个值都 独一无二  
题目数据保证 nums 在预先未知的某个下标上进行了旋转  
\-104<= target<= 104

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array

## 2.思路 ##

（1）二分搜索  
**设计一个时间复杂度为 O(log n) 的搜索方案，最容易想到的应该就是二分搜索**，不过本题中的数组是经过一个升序数组”旋转“之后得到的，只是局部有序。所以在使用二分搜索时，**关键在于分情况判断 target 所在的区间**。

在第一趟的查找过程中，要确定查找区间的开头位置、中间位置以及结尾位置，这里分别定义变量 left、mid 和 right，并赋予相应的值。**这三个变量将整个 nums 数组分为两个部分，即 nums\[left…mid\] 和 nums\[mid…right\]。**

在 left <= right 成立的条件下，分情况进行讨论：

*  **若 nums\[mid\] == target**，直接返回 mid 即可；
 *  **若 nums\[left\] <= nums\[mid\]**：
    
     *  `如果 nums[left] <= target && target < nums[mid]`：这说明 target 一定在 nums\[left…mid\] 之间，按照而二分查找的算法思想，此时的查找区间应变为 nums\[left…mid\]，并且 right = mid - 1，进行下一轮查找；
     *  `如果 nums[left] > target || target >= nums[mid`，这说明 target 在 nums\[mid…right\] 之间，left = mid + 1，进行下一轮查找；
 *  **若 nums\[left\] > nums\[mid\]**：
    
     *  `如果 nums[mid] < target && target <= nums[right]`，这说明 target 在 nums\[mid…right\] 之间，同理变换区间进行查找。
     *  `如果 nums[mid] >= target || target > nums[right]`，这说明 target 在 nums\[left…mid\] 之间，同理变换区间进行查找。

相关题目：  
[LeetCode\_二分搜索\_中等\_81.搜索旋转排序数组 II][LeetCode_81._ II]  
[LeetCode\_二分搜索\_中等\_153.寻找旋转排序数组中的最小值][LeetCode_153.]  
[LeetCode\_二分搜索\_困难\_154.寻找旋转排序数组中的最小值 II][LeetCode_154._ II]

## 3.代码实现（Java） ##

//思路1————二分搜索
    class Solution {
        
        public int search(int[] nums, int target) {
        
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
        
                    return mid;
                }
                // nums[left...mid...high]
                if (nums[left] <= nums[mid]) {
        
    	            // nums[left...mid] 有序
                    if (nums[left] <= target && target < nums[mid]) {
        
                        // target 在 nums[left...mid] 中
                        right = mid - 1;
                    } else {
        
                        // target 在 nums[mid...right] 中
                        left = mid + 1;
                    }
                } else {
        
                	// nums[mid...right] 有序
                    if (nums[mid] < target && target <= nums[right]) {
        
                        // target 在 nums[mid...right] 中  
                        left = mid + 1;
                    } else {
        
                        // target 在 nums[left...mid] 中
                        right = mid - 1;
                    }
                }
            }
            return -1;
        }
    }

[LeetCode_81._ II]: https://blog.csdn.net/weixin_43004044/article/details/120010758
[LeetCode_153.]: https://leetcode.cn/problems/search-in-rotated-sorted-array/
[LeetCode_154._ II]: https://blog.csdn.net/weixin_43004044/article/details/129377572