整数二分

一、算法思想

二分的本质并不是单调性，即：

• 如果有单调性一定可以二分；
• 但二分的题目不一定有单调性。

二分的本质是 边界，其核心在于找到某种性质可以将区间一分为二。

二、算法模板

使用模板时，先通过 check 函数找到等于 mid 的边界，然后分情况判断：

• 若 l = mid，则对应 r = mid - 1，同时计算 mid 时需要 + 1；
• 若 r = mid，则对应 l = mid + 1。

说明

为什么计算 mid 时需要 + 1？

当 l = r - 1 时，mid = l + r >> 1 = l，若更新语句为 l = mid，则区间未变化，会导致死循环，因此需要 + 1 操作。

C++

// 区间 [l, r] 被划分成 [l, mid - 1] 和 [mid, r] 时使用：
int bsearch(int l, int r)
{
    while (l < r) {
        int mid = l + (r - l) / 2 + 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

// 检查 x 是否满足某种性质
bool check(int x) {/* ... */}

// 区间 [l, r] 被划分成 [l, mid] 和 [mid + 1, r] 时使用：
int bsearch(int l, int r)
{
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return r;
}

// 检查 x 是否满足某种性质
bool check(int x) {/* ... */}

Go

func binarySearch(l, r int) int {
    for l < r {
        mid := l + (r-l)/2 + 1
        if check(mid) {
            l = mid
        } else {
            r = mid - 1
        }
    }
    return l
}

func binarySearch(l, r int) int {
    for l < r {
        mid := l + (r-l)/2
        if check(mid) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return r
}

三、代码实战

AcWing 0789

---

题目：数的范围

给定一个按照升序排列的长度为 $n$ 的整数数组，以及 $q$ 个查询。

对于每个查询，返回一个元素 $k$ 的起始位置和终止位置（位置从 $0$ 开始计数）。

如果数组中不存在该元素，则返回 $-1\ -1$。

输入格式

第一行包含整数 $n$ 和 $q$，表示数组长度和询问个数。

第二行包含 $n$ 个整数（均在 $1 \sim 10000$ 范围内），表示完整数组。

接下来 $q$ 行，每行包含一个整数 $k$，表示一个询问元素。

输出格式

共 $q$ 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 $-1\ -1$。

数据范围

$1 \le n \le 100000$

$q \le q \le 10000$

$1 \le k \le 10000$

输入样例：

6 3

1 2 2 3 3 4

3

4

5

输出样例：

3 4

5 5

-1 -1

解答代码：

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    while (m--) {
        int x;
        scanf("%d", &x);
        
        // 二分左边界
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (q[l] != x) {
            printf("-1 -1\n");
        } else{
            printf("%d ", r);
            
            // 二分右边界
            l = 0, r = n - 1;
            while (l < r) {
                int mid = l + (r - l) / 2 + 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", l);
        }
    }
    
    return 0;
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var n, m int
    Fscan(in, &n, &m)

    q := make([]int, n)
    for i := 0; i < n; i++ {
        Fscan(in, &q[i])
    }
    var x int
    for i := 0; i < m; i++ {
        Fscan(in, &x)
        l, r := 0, n-1
        for l < r {
            mid := l + (r-l)/2
            if q[mid] >= x {
                r = mid
            } else {
                l = mid + 1
            }
        }
        if q[r] != x {
            Fprintf(out, "-1 -1\n")
        } else {
            Fprintf(out, "%d ", r)

            l, r = 0, n-1
            for l < r {
                mid := l + (r-l)/2 + 1
                if q[mid] <= x {
                    l = mid
                } else {
                    r = mid - 1
                }
            }
            Fprintf(out, "%d\n", l)
        }
    }
}

func main() {
    run(os.Stdin, os.Stdout)
}