C++二分查找

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++二分查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1979字，纯文字阅读大概需要3分钟。

内容图文

二分查找简介

我们有一个有序序列，这个序列分为前后两个部分，分界点往前都不符合要求，往后都符合要求或者往前都符合要求，往后都不符合要求时，且我们需要在其中找到第一个满足要求或者第一个不满足要求或者最后一个满足要求或者最后一个不满足要求的元素位置时，我们往往会用二分查找来解决。

二分查找，顾名思义，就是每次取左端点和右端点的平均值，判断这个平均值是否符合要求，之后按情况改变左端点或右端点的值，直到左端点大于右端点输出答案（过会儿会详细讲解）。

那为什么不从头到尾枚举一遍呢？如果从头到尾枚举一遍，要是刚开始就有一个元素符合要求，那还好办，万一到最后才有符合要求的可就是On级别的时间复杂度了，可如果用二分查找就只用log2(n)级别了，大大减少了时间复杂度。

举个简单的例子：

题目描述：
给出一段序列和一个k，找出序列中第一个大于等于k的元素的位置。
保证序列为单调递增的序列。

输入格式：
第一行：两个正整数N和k，表示了序列的长度和要比较的值。
第二行：包含N个整数num[i]，描述了这段序列。

输出格式：
一个整数，为第一个符合要求的元素的位置是多少。
如果没有符合要求的数

输入样例：

5 10
1 8 10 10 15

输出样例：

3

二分查找解法

先定义左端点l = 1，右端点r = n。之后开始循环直到左端点大于右端点才停止。循环中每次，取中点（即(l + r) / 2），判断中点是否符合要求，在此题中分界点前为不符合要求的，往后为符合要求的，是形如×××××××√√√√√√的样式，所以如果说中点符合要求（既为√），就让r = mid - 1，并且更新ans的值为mid。否则让l = mid + 1。

想清楚了思路，就可以开始写代码了。

推荐建立一个check函数，这样当要求变得更多时，可以更有利于理清逻辑。

（PS：NR是指序列长度的上限）

# include <cstdio>
# include <iostream>
# include <cmath>
# include <cstring>
# include <algorithm>
using namespace std;

# define FOR(i, a, b) for(int i = a; i <= b; i++)
# define _FOR(i, a, b) for(int i = a; i >= b; i--)

const int NR = 10000;

int n, k;
int a[NR + 10];

bool check(int x){
	return a[x] >= k;
}

int main()
{
	scanf("%d%d", &n, &k);
	FOR(i, 1, n) scanf("%d", &a[i]);
	int l = 1, r = n, ans = -1;
	while(l <= r){
		int mid = (l + r) / 2;
		if(check(mid)) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	printf("%d", ans);
	return 0;
}

God Bless You For Ever!

内容总结

以上是互联网集市为您收集整理的C++二分查找全部内容，希望文章能够帮你解决C++二分查找所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端