一、常用操作
1、头文件
#include <algorithnm>
2、使用方法
(1)binary_search:查找某个元素是否出现
函数模板:binary_search(arr[ ], arr[ ] + size, index)
参数说明:
arr[ ]:数组首地址
size:数组元素个数
index:需要查找的数值
函数功能:在数组中以二分法检索的方式进行查找,若在数组(要求数组元素非递减)中查找到index元素则为真,若查找不到则返回假。
(2)lower_bound:查找第一个元素大于等于某个元素的位置
函数模板:lower_bound(arr[ ], arr[ ] + size, index)
参数说明:
arr[ ]:数组首地址
size:数组元素个数
index:需要查找的数值
函数功能:函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于等于val的第一个元素。如果所有元素都小于val,则返回last的位置,且last的位置是越界的。
(3)upper_bound:查找第一个元素大于某个元素的位置
函数模板:upper_bound(arr[ ], arr[ ] + size, index)
参数说明同上
二、代码
#include <iostream> #include <algorithm> using namespace std; int a[100] = { 4, 10, 11, 30, 69, 70, 96, 100 }; int binarySearch(int x, int n)//n是x数组的长度 { int left = 0; int right = n - 1; while (left <= right) { int mid = (left + right) / 2; if (x == a[mid]) return mid; else if (x > a[mid]) left = mid + 1; else if (x < a[mid]) right = mid - 1; } return -1;//没有找到数据x } //二分搜索递归实现 int recurisonBinarySearch(int left, int right, int x) { if (left > right) return -1; int mid = (left + right) / 2; if (x == a[mid]) return mid; if (x > a[mid]) return recurisonBinarySearch(mid + 1, right, x); else return recurisonBinarySearch(left, mid - 1, x); } int main() { int b = binary_search(a, a + 9, 4);//这个是直接调用库函数 int c = binary_search(a, a + 9, 40); int d = lower_bound(a, a + 9, 10) - a; int e = lower_bound(a, a + 9, 101) - a; int f = upper_bound(a, a + 9, 10) - a; int g = upper_bound(a, a + 9, 101) - a; return 0; }