二分查找 约定不等于承诺〃 2022-08-07 14:47 37阅读 0赞 函数lower\_bound()在first和last中的**前闭后开**区间进行二分查找,返回大于或等于val的**第一个元素**位置。如果所有元素都小于val,则返回**last**的位置 举例如下: 一个数组number序列为:4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标 则 pos = lower\_bound( number, number + 8, 3) - number,pos = 0.即number数组的下标为0的位置。 pos = lower\_bound( number, number + 8, 9) - number, pos = 1,即number数组的下标为1的位置(即10所在的位置)。 pos = lower\_bound( number, number + 8, 111) - number, pos = 8,即number数组的下标为8的位置(但下标上限为7,所以返回最后一个元素的下一个元素)。 所以,要记住:函数lower\_bound()在first和last中的**前闭后开**区间进行二分查找,返回大于或等于val的**第一个元素**位置。如果所有元素都小于val,则返回**last**的位置,且last的位置是越界的!!~ 返回查找元素的第一个可安插位置,也就是“元素值>=查找值”的第一个元素的位置 测试代码如下: **\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain] 1. \#include <iostream> 2. \#include <algorithm> 3. \#include <functional> 4. \#include <vector> 5. 6. using namespace std; 7. 8. 9. int main() 10. \{ 11. const int VECTOR\_SIZE = 8 ; 12. 13. // Define a template class vector of int 14. typedef vector<int > IntVector ; 15. 16. //Define an iterator for template class vector of strings 17. typedef IntVector::iterator IntVectorIt ; 18. 19. IntVector Numbers(VECTOR\_SIZE) ; 20. 21. IntVectorIt start, end, it, location ; 22. 23. // Initialize vector Numbers 24. Numbers\[0\] = 4 ; 25. Numbers\[1\] = 10; 26. Numbers\[2\] = 11 ; 27. Numbers\[3\] = 30 ; 28. Numbers\[4\] = 69 ; 29. Numbers\[5\] = 70 ; 30. Numbers\[6\] = 96 ; 31. Numbers\[7\] = 100; 32. 33. start = Numbers.begin() ; // location of first 34. // element of Numbers 35. 36. end = Numbers.end() ; // one past the location 37. // last element of Numbers 38. 39. // print content of Numbers 40. cout << "Numbers \{ " ; 41. for(it = start; it != end; it++) 42. cout << \*it << " " ; 43. cout << " \}\\n" << endl ; 44. 45. // return the first location at which 10 can be inserted 46. // in Numbers 47. location = lower\_bound(start, end, 1) ; 48. 49. cout << "First location element 10 can be inserted in Numbers is: " 50. << location - start<< endl ; 51. \} #include <iostream> #include <algorithm> #include <functional> #include <vector> using namespace std; int main() { const int VECTOR_SIZE = 8 ; // Define a template class vector of int typedef vector<int > IntVector ; //Define an iterator for template class vector of strings typedef IntVector::iterator IntVectorIt ; IntVector Numbers(VECTOR_SIZE) ; IntVectorIt start, end, it, location ; // Initialize vector Numbers Numbers[0] = 4 ; Numbers[1] = 10; Numbers[2] = 11 ; Numbers[3] = 30 ; Numbers[4] = 69 ; Numbers[5] = 70 ; Numbers[6] = 96 ; Numbers[7] = 100; start = Numbers.begin() ; // location of first // element of Numbers end = Numbers.end() ; // one past the location // last element of Numbers // print content of Numbers cout << "Numbers { " ; for(it = start; it != end; it++) cout << *it << " " ; cout << " }\n" << endl ; // return the first location at which 10 can be inserted // in Numbers location = lower_bound(start, end, 1) ; cout << "First location element 10 can be inserted in Numbers is: " << location - start<< endl ; } [view plain]: http://blog.csdn.net/niushuai666/article/details/6734403#
相关 二分查找 函数lower\_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置 举例 约定不等于承诺〃/ 2022年08月07日 14:47/ 0 赞/ 38 阅读
相关 二分查找 二分查找可以说是在经典不过的查找算法了,比如JAVA的库函数里,就有相应的代码实例。如下写出两个版本的二分查找,非递归和递归的 非递归的 public int bi 系统管理员/ 2022年08月06日 16:24/ 0 赞/ 53 阅读
相关 二分查找 //二分查找 /\ 递归算法 int searchB1(int A\[\], int low, int high, int data); 非递归算法 int 绝地灬酷狼/ 2022年05月12日 01:40/ 0 赞/ 43 阅读
相关 查找——二分查找 基本思想 二分查找是建立在有序顺序表基础上的!步骤如下: 1. 将表中间位置记录的关键字与给定K值进行比较,若两者相等,则查找成功。 2. 蔚落/ 2022年03月27日 03:46/ 0 赞/ 375 阅读
相关 二分查找 二分查找(先排序) typedef struct LNode List; struct LNode{ ElemenType Data[MAXSIZ 爱被打了一巴掌/ 2022年02月02日 17:13/ 0 赞/ 124 阅读
相关 二分查找 使用递归的版本 def bin_search(lst, num, start=None, end=None): """ 二分查找 àì夳堔傛蜴生んèń/ 2022年01月07日 04:03/ 0 赞/ 98 阅读
相关 二分查找 int search2( int array\[\], int n, int v) \{ int left, right, middle; 心已赠人/ 2021年12月20日 16:07/ 0 赞/ 123 阅读
相关 二分查找 二分查找 二分查找是一个比较简单的算法,用 C++ 语言实现如下: template <typename T> int binary_search( ゞ 浴缸里的玫瑰/ 2021年12月13日 03:57/ 0 赞/ 185 阅读
相关 二分查找 > 一、自己实现的 include<iostream> include<cstdio> include<algorithm> u 左手的ㄟ右手/ 2021年09月21日 17:12/ 0 赞/ 290 阅读
还没有评论,来说两句吧...