Search in Rotated Sorted Array

题目大意

把一个严格升序的数组进行旋转，如[0,1,2,3,4,5]旋转3位成为[3,4,5,0,1,2]。在这样的数组中找到目标数字。如果存在返回下标，不存在返回-1。
输入: nums = [4, 5, 6, 7, 0, 1, 2], target = 6 输出: 2
输入: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 输出: -1

解题思路

二分搜索是针对有序数组而言，对于中间有次转折的有序数组，只是要多区分几种情况，二分搜索依然是适用的。
主要就是判断mid的左右哪边是中断的

代码

该解法的判断表达是对称的结构，有助于记忆

class Solution(object):
    def search(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: int """
        left = 0; right = len(nums) - 1
        while left <= right:
            mid = (left + right) / 2
            if target == nums[mid]:
                return mid
            if nums[mid] >= nums[left]:  # 中点大于最左边，说明左边区间没有混乱
                if target < nums[mid] and target >= nums[left]:  # 此时若目标数小于中间数而且大于最左边，说明就在左边区间
                    right = mid - 1
                else:  # 不然就在右边区间
                    left = mid + 1
            else:  # 中点小于最右边，说明右边区间没有混乱
                if target > nums[mid] and target <= nums[right]:  # 此时若目标数大于中间数而且小于最右边，说明就在右边区间
                    left = mid + 1
                else:  # 不然就在左边区间
                    right = mid - 1
        return -1  # 找不到

Search in Rotated Sorted Array II

题目大意

把一个有重复的排序数组进行旋转，如[0,1,1,1,2,3,4,5]旋转3位成为[3,4,5,0,1,1,1,2]。在这样的数组中判断目标数字是否存在。

解题思路

和上题其实唯一的区别在于如果重复的数字中间进行了旋转，所以只要加入

if nums[left] == nums[mid] == nums[right]:
    left += 1
    right -= 1

其他相同。

代码

class Solution(object):
    def search(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: bool """
        left = 0; right = len(nums)-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target: 
                return True
            if nums[left] == nums[mid] == nums[right]:  # 所有指针都一个数字，说明旋转时有的在左边有的在右边，需要往中间看
                left += 1
                right -= 1
            elif nums[mid] >= nums[left]:  # 中点大于最左边，说明左边区间没有混乱
                if target < nums[mid] and target >= nums[left]:  # 此时若目标数小于中间数而且大于最左边，说明就在左边区间
                    right = mid - 1
                else:  # 不然就在右边区间
                    left = mid + 1
            else:  # 中点小于最右边，说明右边区间没有混乱
                if target > nums[mid] and target <= nums[right]:  # 此时若目标数大于中间数而且小于最右边，说明就在右边区间
                    left = mid + 1
                else:  # 不然就在左边区间
                    right = mid - 1
        return False

总结