例题：ACWing 789.数的范围

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

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

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

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

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

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

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

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

数据范围

$1 \leq n \leq 100000$
$1 \leq q \leq 10000$
$1 \leq k \leq 10000$

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

二分查找算法模板

在这里插入图片描述

二分的本质是二段性不是单调性。
二分模板一共有两个，分别适用于不同情况。

算法思路：假设目标值在闭区间[l, r]中，每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1 寻找红色区域的右边界版

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

代码模板：

int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}

版本2 寻找绿色区域的左边界版

当我们将区间[l, r]划分成l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

代码模板：

int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;
}

一些其他细节
为什么需要+1？
原因是如果不加上1，那么mid得到的是下取整的数，那么有可能[mid,r]更新过后mid会一直等于mid（mid + 1 = r的情况）会陷入死循环。
如l = 3, r = 4，则mid = 3 + 4 >>1,mid = 3,若更新为l = mid，则区间[l,r]还是3,4，无限死循环了。

+1之后为什么就不会死循环了呢？
其实我们这里加1实质上实现的操作是上取整，此时就算[mid,r]是m + 1 = r的情况也不会死循环。
如l = 3, r = 4，则mid=3 + 4 + 1 >> 1,mid = 4若更新为l=mid，则区间[l,r]是4,4，会退出循环了。

注： n / i上取整的公式为（n + i - 1）/ i
原因:

n能整除i时,则(i - 1) / i = 0;
n不能整除i时，由于n是整数，则最少也会余1，所以(i - 1 + 大于1小于i的数) / i = 1，实现了上取整。
二分时，n为l + r, i为2，所以就变成了l + r + 1 >> 1;

Java题解

import java.io.BufferedInputStream;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(new BufferedInputStream(System.in));int n = scanner.nextInt(); //数组大小int q = scanner.nextInt();//查询几个数int[] arr = new int[n];for (int i = 0; i < n; i++) { 获取完整数组arr[i] = scanner.nextInt();}for (int i = 0; i < q; i++) {//查询q轮int k = scanner.nextInt();//要查找的数int l = 0, r = n - 1;//初始化 l和 r, 查找左边界while (l < r) {//l=r时才会结束int mid = l + r >> 1;if (arr[mid] >= k) {//寻找所找数的范围的左边界r = mid;} else {l = mid + 1;}}if(arr[l] != k){// 跳出循环时, l = r, 如果数组中不存在 kSystem.out.println("-1 -1");}else{System.out.print(l+" ");//找到了该数的左边界，接下来去找右边界l = 0;// 初始化 l和 r, 查找右边界r = n-1;while(l < r){int mid = l + r + 1 >> 1;if(arr[mid] <= k){l = mid;}else{r = mid - 1;}}System.out.println(l);}}}
}