[LeetCode 笔记] 33. Search in Rotated Sorted Array

前言

　　这题主要运用到二分搜寻法，是 704. Binary Search 的变化题，目标是找到一个旋转阵列中指定元素的阵列，用到一个 while 迴圈和其余 if 判断，时间複杂度估 O(log n)，这里有 JAVA 和 Python 的写法。

题目

There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.

有一个整数阵列 nums 已升序排序 (且具不同的值)。
在传递给你的函数之前，nums 可能在一个未知的枢轴索引 k (1 <= 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，如果 target 它在 nums 中就回传 target 的索引， 如果它不在 nums 中就回传 -1。
你必须写出一个 O(log n) 时间複杂度的演算法。

题目连结：https://leetcode.com/problems/search-in-rotated-sorted-array/

题目限制

1 <= nums.length <= 5000
104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
104 <= target <= 104

範例

Input: nums = [4,5,6,7,0,1,2], target = 0Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3Output: -1

Input: nums = [1], target = 0Output: -1

思路&笔记

这题用的技巧是二分搜寻法，原理是每次循环都会将阵列搜索範围缩小一半，目的是要找到 target 值的 index

初始我们会设定起点位置、终点位置、中间点 (这些是二分搜寻法的必要条件)middle = start + ( end - start ) / 2 可取得中间点如果整个阵列都是有序的，那么目标整数 target 必然存在于该有序的部分，我们可以直接进行二分搜寻找到目标值，但这题比较麻烦的是我们不知道阵列会旋转成什么样子，所以先判断阵列的左边还是右边是否有序如果那半边是有序的，就在那半边使用二分搜寻法做搜寻如果 target 不在那半边的话，则会转向另一边做搜寻直到 start 大于等于 end，表示搜寻範围为空，结束搜寻到最后範围会缩到最小，起点值和目标值一定会重叠，然后回传答案索引

[注意点] 之所以要用上述中间点的写法会比较安全，因如果 start 和 end 趋近于最大数时，两者相加起来的合可能会造成整数溢位

JAVA 实现

class Solution {    public int search(int[] nums, int target) {        int start = 0; // 起点位置        int end = nums.length - 1; // 终点位置        while (start < end) {            int middle = start + (end-start)/2; // 中间点            if (nums[middle] == target) return middle; // 刚好中间点就是答案就回传            // 判断左半边是有序的            if (nums[start] <= nums[middle]) {                // 如果 target 在左半边的範围内，则继续在左半边进行搜寻                if (target >= nums[start] && target < nums[middle]) {                    // 重新定义终点，下次回圈找到新的终点就好                    end = middle - 1;                // 否则，转向右半边进行搜寻                } else {                // 重新定义起点，下次回圈从新的起点开始就好                start = middle + 1;                }            // 否则，右半边是有序的            } else {                if (target > nums[middle] && target <= nums[end]) {                    start = middle + 1;                } else {                    end = middle - 1;                }            }        }        // 到最后範围会缩到最小，起点值和目标值一定会重叠，就回传索引        return nums[start] == target ? start : -1;     }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法
不一样的点是变数的宣告方式不一样，还有 Java 和 Python 的三元运算写法不一样

class Solution:    def search(self, nums: List[int], target: int) -> int:start, end  = 0, len(nums) - 1 # 起点、终点while start < end:middle = start + (end - start) // 2 # 中间点# 中间点是答案就回传if nums[middle] == target return middle # 判断左半边是有序的if nums[start] <= nums[middle]:# 如果 target 在左半边的範围内，则继续在左半边进行搜寻if nums[start] <= target and target < nums[middle]:end = middle - 1else: start = middle + 1 # 否则，转向右半边进行搜寻# 否则，右半边是有序的else:if nums[middle] < target and target <= nums[end]:start = middle + 1else:end = middle - 1# 如果 start == target 回传 start 否则回传 -1return start if nums[start] == target else -1 

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/08/01/LeetCode-33-Search-in-Rotated-Sorted-Array-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论