[Leetcode]Rotated Sorted Array问题

LeetCode上牵扯到Rotated Sorted Array问题一共有四题，主要是求旋转数组的固定值或者最小值，都是考察二分查找的相关知识。在做二分查找有关的题目时，需要特别注重边界条件和跳出条件。在做题的过程中，不妨多设几个测试案例，自己判断一下。

下面是这四题的具体解答。

在求旋转数组中查找固定值，数组中每个数唯一出现。返回查找索引。

class Solution:

    def search(self, nums: List[int], target: int) -> int:

        lo,hi = 0,len(nums)-1

        while lo<=hi:

            mid  = lo+((hi-lo)>>1)

            if nums[mid] == target:

                return mid

            if nums[lo] <= nums[mid]:

                if nums[lo] <= target <= nums[mid]:

                    hi = mid -1

                else:

                    lo = mid + 1

            else:

                if nums[mid] <= target <=nums[hi]:

                    lo = mid + 1

                else:

                    hi = mid - 1

        return -1

在求旋转数组中查找固定值，数组中可能出现重复值。返回True或者False

class Solution(object):

    def search(self, nums, target):

        if not nums:

            return False

        low, high = 0, len(nums) - 1

        while low <= high:

            mid = low+(high-low) // 2

            if target == nums[mid]:

                return True

            if nums[low] < nums[mid]:

                if nums[low] <= target <= nums[mid]:

                    high = mid - 1

                else:

                    low = mid + 1

            elif nums[mid]<nums[low]:

                if nums[mid] <= target <= nums[high]:

                    low = mid + 1

                else:

                    high = mid - 1

            else:

                low+=1

        return False

在求旋转数组中查找最小值，数组中每个数唯一出现。返回最小值。

class Solution:

    def findMin(self, nums: List[int]) -> int:

        lo,hi = 0,len(nums)-1

        if nums[lo] < nums[hi]:return nums[lo] # 递增

        while hi-lo > 1:

            mid = lo+(hi-lo)//2

            if nums[lo] > nums[mid]:

                hi = mid

            elif nums[hi] < nums[mid]:

                lo = mid

        return nums[hi]

在求旋转数组中查找最小值，数组中可能出现重复值。返回最小值。

class Solution:

    def findMin(self, nums: List[int]) -> int:

        if not nums:return

        lo,hi = 0,len(nums)-1

        if nums[lo] < nums[hi]:return nums[lo] # 递增

        minVal = nums[lo]

        while hi-lo>1:

            mid = lo+(hi-lo)//2

            if nums[lo] > nums[mid]:

                hi = mid

            elif nums[hi] < nums[mid]:

                lo = mid

            elif nums[mid] == nums[lo] == nums[hi]:

                for i in range(lo,hi):

                    if nums[i] < minVal:

                        minVal = nums[i]

                        hi = i

                return minVal

        return nums[hi]