[挑战程序设计]二分搜索

[挑战程序设计]二分搜索

第一个抽签的问题，判断从口袋放回的拿出n个数，和是否可能为m。

一、可以写四重循环。

但是当n的范围1<=n<=1000时，时间复杂度太高，考虑

二、二分搜索与O（n^3logn）

int n,m,k[MAX_N];bool binary_search(int x){ int l=0,r=n; while(r-l>=1){ int i=(l+r)/2; if(k[i]==x) return true; else if(k[i]

STL中的binary_search:

bool binary_search(ForwardIterator first, ForwardIteratorlast, const T& value, StrictWeakOrdering comp);

在[first,last)中查找value，如果找到返回Ture,否则返回False。

还有一个：

equal_range是C++ STL中的一种二分查找的算法，试图在已排序的[first,last)中寻找value，它返回一对迭代器i和j，其中i是在不破坏次序的前提下，value可插入的第一个位置（亦即lower_bound），j则是在不破坏次序的前提下，value可插入的最后一个位置（亦即upper_bound），因此，[i,j)内的每个元素都等同于value，而且[i,j)是[first,last)之中符合此一性质的最大子区间

三、O（n^2logn）算法

kc+kd=m-ka-kb。

这种情况不能使用二分搜索，但如果先枚举出Kc+Kd的n^2个数字并排好序。

int n,m,k[MAX_N];int kk[MAX_N*MAX_N];bool binary_search(int x){ int l=0,r=n*n; while(r-l>=1){ int i=(l+r)/2; if(kk[i]==x) return i+1; else if(kk[i]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。