C++ 标准模板库 (STL) 中的二分查找
c++server side programmingprogramming更新于 2024/9/8 4:33:00
二分查找又称为对数查找，是一种在已排序数组中查找元素的搜索算法。该算法递归地将数组分成两半，如果在中间位置找到元素，则返回，否则调用除法并再次检查，直到找到元素。
工作原理
该算法通过将排序数组的中间元素与要搜索的元素进行比较来工作。
如果搜索元素等于中间元素，则返回元素的索引。
如果搜索元素大于中间元素，则在左子数组中搜索，即从中间的下一个元素到数组末尾的子数组。
如果搜索元素小于中间元素，则在右子数组中搜索，即从第一个元素到中间元素之前的元素的子数组数组。
语法
调用标准二进制排序，使用以下语法 −
binary_search(start_address , end_address , element)
参数
start_address 是数组第一个元素的地址。
end_address 是数组最后一个元素的地址。
element 是要在数组中找到的元素。
返回
如果找到，则返回一个整数，其值等于数组中元素的索引，否则返回 0。
示例
#include <algorithm>
#include <iostream>
using namespace std;
void printArray(int a[], int arraysize){
for (int i = 0; i < arraysize; ++i)
cout << a[i] << &" &";;
}
int main(){
int arr[] = {1 , 5, 9, 7 , 3, 2 , 0 , 4};
int sizeofarr = sizeof(arr)/sizeof(arr[0]);
cout<<"数组的元素为 :\n";
printArray(arr , sizeofarr);
cout<<"\n对数组元素进行排序。";
sort(arr , arr+sizeofarr);
cout<<"\n排序后的数组为:";
printArray(arr, sizeofarr);
cout<<"\n要搜索的元素为 4";
if(binary_search(arr , arr+sizeofarr , 4))
cout<<"\n找到元素";
else
cout<<"\n元素未找到";
}
输出
数组元素为: 1 5 9 7 3 2 0 4 对数组元素进行排序。 排序后的数组为:0 1 2 3 4 5 7 9 要搜索的元素为 4
