c++ stl二分查找与lower_bound
2021/6/2 20:51:16
本文主要是介绍c++ stl二分查找与lower_bound,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- binary_search实现
int myBinary_search(int arr[], int n, int target) { int first = 0, last = n; int mid; while (first < last) { mid = first + (last - first) / 2; if (arr[mid] == target) { return mid; } else if ( target > arr[mid] ) { first = ++mid; } else { last = mid; } } return -1; } void test() { int arr[] = { 5,7,7,8,8,10 }; cout << myBinary_search(arr, 6, 1) << endl; //-1 cout << myBinary_search(arr, 6, 5) << endl; //0 cout << myBinary_search(arr, 6, 8) << endl; //3 cout << myBinary_search(arr, 6, 10) << endl;//5 }
- lower_bound实现
template<typename ForwardIter, typename T> ForwardIter myLower_bound(ForwardIter first, ForwardIter last, T value) { while (first != last) { auto mid = next(first, distance(first, last) / 2); if (value > *mid) first = ++mid; else last = mid; } return first; } template<typename ForwardIter, typename T> ForwardIter myUpper_bound(ForwardIter first, ForwardIter last, T value) { while (first != last) { auto mid = next(first, distance(first, last) / 2); if (value >= *mid) first = ++mid; else last = mid; } return first; }
- cppreference.com
//可能的实现 //版本一 template<class ForwardIt, class T> bool binary_search(ForwardIt first, ForwardIt last, const T& value) { first = std::lower_bound(first, last, value); return (!(first == last) && !(value < *first)); } //版本二 template<class ForwardIt, class T, class Compare> bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp) { first = std::lower_bound(first, last, value, comp); return (!(first == last) && !(comp(value, *first))); }
myBinary_search根据lower_bound实现
这篇关于c++ stl二分查找与lower_bound的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享