题目

搜索旋转排序数组

思路

此题是很明显的二分法求确切值，思考方法跟求边界值略有不同

  • 首先可以确定循环条件为$[left,right]$，因为既然是求明确值，那么肯定是$left$和$right$的闭区间（$left$和$right$的值也被包含进去）
  • 然后再确定左右边界的移动方式
    • 假定当前$mid$不符合（$left$右移），此时可能符合条件的区间应$[mid+1, right]$（需要将$mid$排除在外，因为$mid$已经不符合了）
    • 同理当$mid$不符合（$right$左移）也是一样，此时符合区间应为$[left,mid-1]$

再回归到此题，此题的不同之处是，将原本有序的序列进行了旋转，变为了两个有序的序列，乍看起来不太好做，实际上一分析，做法还是相同，只要根据条件判断每一次$left$右移和$right$左移的条件就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        lv = nums[0]
        while left <= right:
            mid = left + (right - left) // 2
            t = nums[mid]
            if t == target:
                return mid
            if target >= lv:  # 左半边
                if nums[left] <= t < target:  # 右移
                    left = mid + 1
                else:
                    right = mid - 1
            else:  # 右半边
                if nums[right] >= t > target:  # 左移
                    right = mid - 1
                else:
                    left = mid + 1
        return -1