欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

c++ STL 二分查找(binary search)

程序员文章站 2024-03-17 19:29:34
...

二分查找是一种广泛使用的搜索算法,它要求在应用搜索之前对数组进行排序。该算法的主要思想是继续将数组分成两半(分而治之),直到找到元素,或者用尽所有元素。

它通过将数组的中间项与目标进行比较来工作,如果匹配,则返回true;否则,如果中间项大于目标,则在左子数组中执行搜索。

如果中间项小于目标,则在右子数组中执行搜索。

函数原型

binary_search(startaddress, 
              endaddress, valuetofind)

startaddress: 列表起始地址
endaddress: 列表末尾地址
valuetofind: 查找的目标值

基本类型

// CPP program to implement
// Binary Search in
// Standard Template Library (STL)
#include <algorithm>
#include <iostream>

using namespace std;

void show(int a[], int arraysize)
{
	for (int i = 0; i < arraysize; ++i)
		cout << a[i] << ",";
}

int main()
{
	int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
	int asize = sizeof(a) / sizeof(a[0]);
	cout << "\nThe array is : \n";
	show(a, asize);

	cout << "\n\nLet's say we want to search for ";
	cout << "\n2 in the array So, we first sort the array";
	sort(a, a + asize);
	cout << "\n\nThe array after sorting is : \n";
	show(a, asize);
	cout << "\n\nNow, we do the binary search";
	if (binary_search(a, a + 10, 2))
		cout << "\nElement found in the array";
	else
		cout << "\nElement not found in the array";

	cout << "\n\nNow, say we want to search for 10";
	if (binary_search(a, a + 10, 10))
		cout << "\nElement found in the array";
	else
		cout << "\nElement not found in the array";

	return 0;
}

输出

The array is : 
1,5,8,9,6,7,3,4,2,0,

Let's say we want to search for 
2 in the array So, we first sort the array

The array after sorting is : 
0,1,2,3,4,5,6,7,8,9,

Now, we do the binary search
Element found in the array

Now, say we want to search for 10
Element not found in the array

自定义类型

二分查找其通过比较加速查找,其核心也是调用的比较函数,所以二分查找和排序一样,自定义类型依赖比较函数的实现

比较函数实现,参考sort

// CPP program to implement
// Binary Search in
// Standard Template Library (STL)
#include <algorithm>
#include <iostream>

using namespace std;

struct MyFav {
    int x;
    int y;
    bool operator<(const MyFav& fav) const {
        return this->x < fav.x;
    }
};

void show(MyFav arr[], int lenth) {
    for(int i=0; i<lenth; i++) {
        cout << arr[i].x << ", " << arr[i].y << endl;
    }
}

int main()
{
	MyFav a[] = {{2, 3}, {5, 1}, {3, 4}, {1, 8}};
	int asize = sizeof(a) / sizeof(a[0]);
	cout << "\nThe array is : \n";
	show(a, asize);

	cout << "\n\nLet's say we want to search for ";
	cout << "\n2 in the array So, we first sort the array";
	sort(a, a + asize);
	cout << "\n\nThe array after sorting is : \n";
	show(a, asize);
	cout << "\n\nNow, we do the binary search";
	if (binary_search(a, a + asize, MyFav{2, 0}))
		cout << "\nElement found in the array";
	else
		cout << "\nElement not found in the array";

	cout << "\n\nNow, say we want to search for 10";
	if (binary_search(a, a + asize, MyFav{10, 0}))
		cout << "\nElement found in the array";
	else
		cout << "\nElement not found in the array";

	return 0;
}

输出

The array is :
2, 3
5, 1
3, 4
1, 8


Let's say we want to search for
2 in the array So, we first sort the array

The array after sorting is :
1, 8
2, 3
3, 4
5, 1


Now, we do the binary search
Element found in the array

Now, say we want to search for 10
Element found in the array