刘老师的修道场
0%

二分

发表于 更新于 分类于

最基本的模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func bSearch(a []int, target int) int {
    left := 0
    right := len(a) - 1

    for left <= right {
        mid := left + (right - left)/2
        if a[mid] == target {
            return mid
        } else if a[mid] < target {
            left = mid + 1
        } else if a[mid] > target {
            right = mid - 1
        }
    }
    return -1
}

另外一类问题

数组中可能有重复的值找最左边的
数组中可能有重复的值找最右边的
找小于等于某个数最右下标
找大于等于某个数最左下标

这四个问题的共同点是如果不加左右的限制，符合条件的值可能不止一个，
找到一个符合条件的值，左右可能还有符合条件的值，用标准的模版
不好处理，但是可以把当前符合条件的解记录下来，然后根据条件调整区间

找最左的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func leftBSearch(a []int, target int) int {
    left := 0
    right := len(a) - 1
    ans := -1

    for left <= right {
        mid := left + (right - left)/2
        if a[mid] == target {
            ans = mid
            // 先把存在解记录下来
            right = mid - 1
            // 调整区间，因为要找最左，区间往左调整
        } else if a[mid] < target {
            left = mid + 1
        } else if a[mid] > target {
            right = mid - 1
        }
    }
    return ans
}

找最右的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func leftBSearch(a []int, target int) int {
    left := 0
    right := len(a) - 1
    ans := -1

    for left <= right {
        mid := left + (right - left)/2
        if a[mid] == target {
            ans = mid
            // 先把存在解记录下来
            left = mid + 1
            // 调整区间，因为要找最右，区间往右调整
        } else if a[mid] < target {
            left = mid + 1
        } else if a[mid] > target {
            right = mid - 1
        }
    }
    return ans
}

找小于等于target最右下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func mostRightLe(a []int, target int) int {
    left := 0
    right := len(a) - 1
    ans := -1

    for left <= right {
        mid := left + (right - left)/2

        if a[mid] <= target {
            ans = mid
            // 先把存在解记录下来

            left = mid + 1
            // 调整区间，因为要找最右，区间往右调整
        } else {
            right = mid - 1
        }
    }
    return ans
}

找大于等于target最左下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func mostLeftGe(a []int, target int) int {
left := 0
right := len(a) - 1
ans := -1

    for left <= right {
        mid := left + (right - left)/2

        if a[mid] >= target {
            ans = mid
            // 先把存在解记录下来

            right = mid - 1
            // 调整区间，因为要找最左，区间往左调整
        } else {
            left = mid + 1
        }
    }
    return ans
}