C++数组搜索（二分法）

灯珑LoGin

发布于 2022-10-31 10:15:37

2210

发布于 2022-10-31 10:15:37

文章被收录于专栏：龙进的专栏

如果我们希望判断某个元素是否存在于一个array中，我们可以使用binary_search方法。

需要注意的是，binary_search方法是二分搜索，而根据二分搜索的原理我们可以知道，二分搜索的前提是，数组已经按照升序进行排序。

ps：二分搜索每次检查的数据量是前一次的一半，从而达到高效搜索。

上代码！（本代码使用了C++11的新特性，所以需要在较新版本的ide中才能正常编译）

#include<iostream>
#include<iomanip>
#include<array>
#include<string>
#include<algorithm>
using namespace std;

int main()
{
	const size_t arraySize = 7;
	array<string, arraySize> colors = { "red", "orange", "yellow", "green", "blue", "indigo", "violet" };
	cout << "Unsorted array:\n";
	for (string s : colors)
		cout << s << " ";
	cout << endl;
	sort(colors.begin(), colors.end());	//由于本程序采用二分搜索，根据二分搜索的前提，数组需要经过升序排序，否则返回的结果不确定
	cout << "sorted array:\n";
	for (string s : colors)
		cout << s << " ";

	//search for "indigo" in colors
	bool found = binary_search(colors.begin(), colors.end(),"indigo");
	cout << "\n\n\"indigo\"" << (found ? "was " : "was not " )<< "found in colors" << endl;

	found = binary_search(colors.begin(), colors.end(), "cyan");
	cout << "\n\n\"indigo\"" << (found ? "was " : "was not ") << "found in colors" << endl;


}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020年10月12日，如有侵权请联系 cloudcommunity@tencent.com 删除

c++