Leetcode 33. 搜索旋转排序数组

心路历程:

这道题的核心在于"如果左半段递增则一定nums[l] < nums[mid]"这个充要条件，并且右半段是没法根据这一点进行判断的，每次在二分搜索中，只需要判断target是否落入递增区间即可.

二分法思想核心:
target一定在这个里面
否则target一定在另外一边

注意的点:

1、建议全部按照闭区间去思考二分法, 这样每次更新l, r都是按照+1 -1 去更新,防止出现死循环
2、这道题最好按照左侧数组上升还有右侧数组上升的情况进行判断, 否则else的条件判断会十分复杂

解法: 二分搜索

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        # 二分查找法； 这道题只能判断左侧是不是上升
        l, r = 0, n -1
        while r >= l:  # 这里用等号可以避免最后再去判断 nums[l] == target
            print(l, r)
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] >= nums[l]:  # 代表数组左侧上升
                if nums[l] <= target < nums[mid]: r = mid - 1
                else: l = mid + 1
            else:  # 代表右侧数组上升
                if nums[mid] < target <= nums[r]: l = mid + 1
                else: r = mid - 1
        # if nums[l] == target: return l
        return -1