河南郑州汽车网网站建设,网站哪里有做的,广西seo,图片链接生成器软件二分查找的前提
库函数只能对数组进行二分查找。 对一个数组进行二分查找的前提是这个数组中的元素是单调的。 一般为单调不减#xff0c;当然如果是单调不增也可以(需要修改比较函数)
例如: [1#xff0c;5#xff0c;5#xff0c;9#xff0c;18]是单调的
[1 , 9, 9,…二分查找的前提
库函数只能对数组进行二分查找。 对一个数组进行二分查找的前提是这个数组中的元素是单调的。 一般为单调不减当然如果是单调不增也可以(需要修改比较函数)
例如: [155918]是单调的
[1 , 9, 9, 7, 15]不是单调的
[988771]是单调的
binary_search函数
binary_search是C标准库中的一个算法函数用于在已排序的序列(例如数组或容器vector)中查找特定元素。
它通过二分查找算法来确定序列中是否存在目标元素。
函数返回一个bool值表示目标元素是否存在于序列中。
如果需要获取找到的元素的位置可以使用std::lower_bound函数或std::upper_bound函数。
vector int numbers {1, 3, 5 , 7 ,9};int target 5;bool found binary_search(number.begin(),number.end(),target);if(found){cout Target element target found. endl;
}else{cout Target element target not found. endl;
}lower_bound和upper_bound
前提:数组必须为非降序
如果要在非升序的数组中使用可以通过修改比较函数实现(方法与sort自定义比较函数类似)
lower_bound(st,ed,_x)返回地址[st, ed)中第一个大于等于x的元素的地址
upper_bound(st,ed,x)返回地址[st,ed)中第一个大于x的元素的地址
如果不存在则返回最后一个元素的下一个位置在vector中即end()
地址-首地址下标
[lower_bound , upper_bound)
//初始化
vector int v{5,1,7,3,10,18,9};
//排序
sort(v.begin(),v.end());
for(auto i : v)cout icout\n;
//找到数组中第一个大于等于8的元素的位置
cout(lower_bound(v.begin(),v.end(),8)- v.begin())\n;例题
#include bits/stdc.h
using namespace std;
int main(void)
{int data[200];for(int i 0 ; i 200 ; i )data[i] 4 * i 6;int target 0;cin target;cout (lower_bound(data,data200,target)- data);return 0;
}
