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
30
31
32
33
34
35
36

// @Title: 搜索旋转排序数组 (Search in Rotated Sorted Array)
// @Author: 15816537946@163.com
// @Date: 2020-11-04 22:41:45
// @Runtime: 4 ms
// @Memory: 2.5 MB
func search(nums []int, target int) int {
	nLen := len(nums)
	if nLen == 0 {
		return -1
	}

	l, r := 0, nLen-1
	for l <= r {
		mid := (l + r) >> 1
		// mid := (l + r) / 2
		if nums[mid] == target {
			return mid
		}

		if nums[0] <= nums[mid] {
			if nums[0] <= target && target < nums[mid] {
				r = mid - 1
			} else {
				l = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[nLen-1] {
				l = mid + 1
			} else {
				r = mid - 1
			}
		}
	}
	return -1
}