二分算法--整数二分

二分算法–整数二分

假如给定一个整数序列，{ $a_1$ , $a_2$ , $a_3$ , …, $a_n$ }

我们将整个数列根据某个元素 $a_x$ 将数列分成左右两个部分（某一部分可以包含 $a_x$ ）

在这里插入图片描述

首先我们定义一个mid

如果check()函数是判断蓝色规则

check(mid)为true，也就是mid元素在蓝色框框中，我们更新边界为[mid, r]
check(mid)为false，也就是mid元素不在蓝色框框中，我们更新边界为[l, mid - 1]

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

这里解释一下为什么求mid的时候要加1，我们知道/号是向下整除，如果此时 l = r - 1，而且check(x)为true时

mid = （r - 1 + r）/ 2 = l

l = mid = l，此时就会形成死循环

如果check()函数是判断红色规则

check(x)为true，也就是mid元素在红色框框中，我们更新边界为[l, mid]
check(x)为false，也就是mid元素不在红色框框中，我们更新边界为[mid + 1， r]

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

【例题】

给定一个按照升序排列的长度为 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

C++代码

#include <iostream>
using namespace std;
const int N = 100010;
int m,n;
int q[N];
int main(){scanf("%d",&n);scanf("%d",&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 >> 1;if(q[mid] >= x) r = mid;else l = mid + 1;}if(q[l] != x) cout << "-1 -1" << endl;else{cout << l << ' ';int l = 0, r = n - 1;while(l < r){int mid = l + r + 1 >> 1; if(q[mid] <= x) l = mid;else r = mid - 1;}cout << l << endl;}}return 0;
}

Java代码

import java.util.Scanner;
public class Main {static final int N = 100010;static int m, n;static int[] q = new int[N];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();for (int i = 0; i < n; i++) {q[i] = scanner.nextInt();}while (m-- > 0) {int x = scanner.nextInt();int l = 0, r = n - 1;while (l < r) {int mid = l + r >> 1;if (q[mid] >= x) {r = mid;} else {l = mid + 1;}}if (q[l] != x) {System.out.println("-1 -1");} else {System.out.print(l + " ");l = 0;r = n - 1;while (l < r) {int mid = l + r + 1 >> 1;if (q[mid] <= x) {l = mid;} else {r = mid - 1;}}System.out.println(l);}}scanner.close();}
}