33. Search in Rotated Sorted Array

这道题一开始看半天没有弄明白
后来恍然大悟
直接看注释
基于常规二分查找算法
重点在于 我们确定lr边界变化的时候需要考虑mid所在不同分段存在不同情况

class Solution(object):
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if target == nums[mid]:
                return mid
            if nums[mid] < nums[-1]: # mid 位于右段
                if nums[mid] <= target <= nums[-1]: # 为什么选择这个判断条件？ 是因为这一段容易判断 二分时 我们需要根据target所在mid的左半部分还是右半部分进行lr边界的变换 我们可以发现右半段的判断更加简单 左半部分包含两种情况 比较复杂
                    left = mid + 1
                else:
                    right = mid - 1
            else: # mid 位于左段
                if nums[0] <= target <= nums[mid]: # 同理 实测 等号随便取
                    right = mid - 1
                else:
                    left = mid + 1
        return -1

还有一种解法

• 找到反转的index
• 运用数组的反转的二分查找

class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        index = left
        # print(index)

        # The usual binary search and accounting for rotation. 旋转数组的二分查找 需要知道旋转的多少
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            realmid = (mid + index) % len(nums)
            if nums[realmid] == target:
                return realmid
            if nums[realmid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1