二分查找.md

二分查找

参考：https://www.acwing.com/blog/content/31/

二分模板一共有两个，分别适用于不同情况。

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

假设数组 arr = [1, 2, 3, 3, 3, 5]

版本1

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

• 返回结果为 第一个 大于等于 某个数的 下标

arr = [1,2,3,3,3,5]

def binarySearch1(k): # lower_bound,
    l, r = 0, len(arr) - 1
    while l < r:
        mid = l + r >> 1
        if arr[mid] < k:
            l = mid + 1
        else:
            r = mid
    return l

print(binarySearch1(0))
print(binarySearch1(1))
print(binarySearch1(2))
print(binarySearch1(3))
print(binarySearch1(4))
print(binarySearch1(5))
print(binarySearch1(6))
'''
0
0
1
2
5
5
5
'''

版本2

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

• 返回结果为 最后一个 小于等于 某个数的 下标

def binarySearch2(k): 
    l, r = 0, len(arr) - 1
    while l < r:
        mid = (l + r + 1) >> 1
        if arr[mid] <= k:
            l = mid
        else:
            r = mid - 1
    return l

print(binarySearch2(0))
print(binarySearch2(1))
print(binarySearch2(2))
print(binarySearch2(3))
print(binarySearch2(4))
print(binarySearch2(5))
print(binarySearch2(6))
'''
0
0
1
4
4
5
5
'''

Acwing789. 数的范围

https://www.acwing.com/problem/content/description/791/

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

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

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

输入格式

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

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

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

输出格式

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

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

数据范围

1≤n≤100000

1≤q≤10000

1≤k≤10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static int[] arr, queries;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str = reader.readLine();
        String[] line1 = str.split(" ");
        int n = Integer.parseInt(line1[0]);
        int q = Integer.parseInt(line1[1]);
        String[] strArr = reader.readLine().split(" ");
        arr = new int[strArr.length];
        queries = new int[q];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(strArr[i]);
        }
        
        int t = 0;
        while (q-- > 0) {
            queries[t++] = Integer.parseInt(reader.readLine());
        }
        while (t-- > 0) {
            // 二分查找 用两套模板找到第一个和最后一个 大于等于/小于等于 某个数的下标
            int x = queries[queries.length - t - 1];
            System.out.println(bsFindLeft(x) + " " +bsFindRight(x));
        }
    }

    public static int bsFindLeft(int x) {	// 模板1
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (arr[mid] < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return arr[left] == x ? left : -1; // 最后left和right会重合，检查一下有没有找到x
    }

    public static int bsFindRight(int x) {	 // 模板2
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (left + right + 1) >> 1; // 防止死循环
            if (arr[mid] <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return arr[left] == x ? left : -1;    // 最后left和right会重合，检查一下有没有找到x
    }
}