33. Search in Rotated Sorted Array

题意：一个已排序的数组在每个位置被翻转了，在这个数组中查找一个数字

思路： 二分法的变形，注意边界条件的检验，写错了很多次，检查的时候，应该假设某一半是单调递增区间，然后让target在该区间为一种情况，不在该区间为一种情况

Python：

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
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 5 star, 二分法,
        # 这个是先比较左右两边和中间的大小，分类讨论来进行排除一半，然后比较中间的和目标数字
        left, right = 0, len(nums) - 1
        while left <= right:
            middle = (left+right)//2
            if nums[middle] == target:
                return middle
            if nums[middle] >= nums[left]:
                if nums[middle] > target >= nums[left]:
                    right = middle - 1
                else:
                    left = middle + 1
            elif nums[right] > nums[middle]:
                if nums[right] >= target > nums[middle]:
                    left = middle + 1
                else:
                    right = middle - 1

        return -1

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
func search(nums []int, target int) int {
	var mid int
	length := len(nums)
	left, right := 0, length-1
	for left <= right {
		mid = (left+right)/2
		if nums[mid] == target {
			return mid
		}
		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 -1

}