跳转至

LC33 - 搜索旋转排序数组

SearchInRotatedSortedArray.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
package BinarySearch

func search(nums []int, target int) int {
    for l, r := 0, len(nums)-1; l <= r; {
        m := l + (r-l)/2
        if nums[m] == target {
            return m
        }
        if nums[l] <= nums[m] {
            if nums[l] <= target && target < nums[m] {
                r = m - 1
            } else {
                l = m + 1
            }
        } else {
            if nums[m] < target && target <= nums[r] {
                l = m + 1
            } else {
                r = m - 1
            }
        }
    }
    return -1
}

// (1) "有序数组" 属于 "旋转排序数组"
// (2) 对于旋转排序数组[l,r]以及某个划分点m, 必有[l,m]与[m,r]其一是旋转排序数组，其二是有序数组

26 - 27行的两个结论是理解旋转排序数组的关健，LC153 (下一题) 也会用到。