81. Search in Rotated Sorted Array II

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

思路：二分法，重点是二分之后，必然有一半是有序的，对target在有序的那一半比较是一种情况，在另一半是另一种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        # 二分查找的变形 6 star, 边界条件比较难以考虑周全
        left, right = 0, len(nums) - 1
        while left <= right:
            middle = (left+right)//2
            if nums[middle] == target:
                return True
            if nums[middle] == nums[left] == nums[right]: # 注意这个条件
                left += 1
                right -= 1
            elif nums[middle] >= nums[left]:
                if target < nums[middle] and target >= nums[left]:  # 注意target和两边都进行了比较
                    right = middle - 1
                else:
                    left = middle + 1
            elif nums[right] >= nums[middle]:
                if target > nums[middle] and target <= nums[right]:
                    left = middle + 1
                else:
                    right = middle - 1
        return False

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func search(nums []int, target int) bool {
	var mid int
	length := len(nums)
	left, right := 0, length-1
	for left <= right {
		mid = (left+right)/2
		if nums[mid] == target {
			return true
		}
		if nums[left] == nums[right] && nums[left] == nums[mid] { //特殊情况
			left++
			right--
		} else if nums[mid] >= nums[left] {
			if nums[mid] > target && target >= nums[left]{ // left到mid是单调递增, target是在left到mid的区间
				right = mid - 1
			} else {
				left = mid + 1
			}

		} else if nums[right] >= nums[mid] {
			if nums[right] >= target && target > nums[mid]{ // mid到right是单调 递增
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return false
}