二分搜索的基本相关问题

标签: 二分搜索 相关 问题 | 发表时间:2013-04-25 09:20 | 作者:heat nan
出处:http://www.cnblogs.com/

二分查找是基于分治思想的一种算法,所谓分治思想就是将一些规模很大难于直接解决的问题,缩小为一个较小的问题就很容易解决的思想,(当然它的子问题仍可以继续分解为相同的子问题)。归结为一句话就是:“以大化小,各个击破,分而治之,组合取果”。


二分查找作为一种高效的查找算法,是解决一些有序序列查找的不二之选。但他的缺点也就是使用于有序的数组,有一定的局限性。但二分在一些高效的程序设计中往往被用作优化的利器。因此,熟练应用二分查找是必须的。


二分查找的实现:比如有一列数从1到100,已经排好序,我们要查找25,按照传统的逐个遍历,需要查找25次,而采用二分查找的方法,首先那25和这组数列的中间的数做比较50,结果查找数小于中间数,所以区间【50-100】的数就可以舍弃了,然后查找范围就缩减为了【1-49】,接下来仍然那25和查找区间的中间数25做比较,显然这样已经查找到了,这样只需要2次就查找到了,而普通的查找方法需要25次。


假设其数组长度为n,其算法复杂度为o(log(n)),灰常高效。

 


【二分算法的非递归实现】


这个可能就是C++中STL库中的那个。



 1 int BinarySearch(int a[],int n,int x)//a[]待查找数组 n查找范围 x被查找数     
2 {
3 int low=0;//查找区间 起点
4 int high=n-1;//查找区间 终点
5 while(low<=high)
6 {
7 int mid=(low+high)/2;
8 if(x==a[mid])//如果查找成功 返回其下标
9 return mid;
10 else if(x>a[mid])
11 low=mid+1;
12 else if(x<a[mid])
13 high=mid-1;
14 }
15 return -1;//查找失败
16 }


 


【STL中的binary_search】


当然,如果是纯粹的二分搜索,可以直接调用algorithm中的二分搜索函数,上面的就都省了。、


强大的C++标准模板库中提供有二分查找函数,直接调用可以节省时间:


binary_search(num,num+n,key);


这里的参数num指查找序列(已经排过序),num-num+n指查找范围,key指待查找的值。


如果查找成功则返回true,否则返回false。


 


 


【二分搜索的递归实现】



 1 int BinarySearch(int a[],int x,int low,int high)//a[]待查找数组 low/high查找范围 x被查找数     
2 {
3 if(low>high) return -1;
4
5 int mid=(low+high)/2;
6 if(x==a[mid])//如果查找成功 返回其下标
7 return mid;
8 else if(x>a[mid])
9 BinarySearch(a,x,mid+1,high);
10 else if(x<a[mid])
11 BinarySearch(a,x,low,mid-1);
12
13 }


二分作为一种基本的算法,在程序设计题中往往不会单独用到,而更像是一种工具,常用作一些问题的优化。

本文链接

相关 [二分搜索 相关 问题] 推荐:

二分搜索的基本相关问题

- - 博客园_首页
二分查找是基于分治思想的一种算法,所谓分治思想就是将一些规模很大难于直接解决的问题,缩小为一个较小的问题就很容易解决的思想,(当然它的子问题仍可以继续分解为相同的子问题). 归结为一句话就是:“以大化小,各个击破,分而治之,组合取果”. 二分查找作为一种高效的查找算法,是解决一些有序序列查找的不二之选.

相关性问题

- - 扯氮集--上海魏武挥的博客 - 扯氮集--上海魏武挥的博客
人的本性是趋利避害的,任何合作(或者交易,或者搭伙,或者配对,反正就不是一个人干的事)都会存在三个可能:有利、有害、无利无害. 对于合作一方来说,至少应该保持一个无害的结果,这是常识. 如果觉得有害的可能性很大,于是,我们就会拒绝合作. 问题在于,谁也不是神仙,没有人可以事先100%断定合作必然会有利或至少无害,于是人们需要很多背景信息来供决策.

paypal相关问题

- - 牛B博客 niub.us
paypal ,号称是全球最大的网络支付公司,在国外确实很强,不过在国内被支付宝干掉了. paypal在国内中文名叫贝宝,国内有了支付宝一般人基本上用不上这玩意,今天文章里和大家说说paypal国际版的问题. 因为今年3月份,全球最大的电子商务平台ebay(曾经,现在是淘宝了)搞了一个海淘节(专门针对中国买家),很多数码产品、手表、包包等都有非常实惠的价格.

二分搜索总结

- - CSDN博客推荐文章
对于二分搜索,一般的程序员都不陌生了,大部分都会认为是小菜一碟了,其实不然,据《编程珠玑》上说,这个算法的第一篇论文1946年就发表了,但是第一个没有错误的二分程序再1962年才出现,所以相信,对于这个算法,大家即使烂熟于心,但是如果没有亲自动手写过,还是会出现不少问题的. 有一个有序整数数组,给定一个整数,请从数组中找出这个整数出现的位置,如果这个整数出现多次,返回其中一个位置.

MySQL Temporary Table相关问题的探究

- comain - 淘宝核心系统团队博客
让我们先来观察几条非常简单的MySQL语句:. 这是丁奇提出的引导性的问题,几条语句看似简单,不过接下来我们提出的一连串问题与进. 看到以上语句,你很容易会产生类似于以下的疑问:. 上述语句在一个session中先后创建了两个名为’tmp’的table,只不过一个是temporary. table,一个是normal table.

Windows下ADB使用相关问题

- - CSDN博客移动开发推荐文章
Windows下ADB使用相关问题. 在Windows XP,WIN7下均可按本文操作进行;WIN8下没有进行实验,但操作设置大致相同,除了第4步,adb_usb.ini的位置可能有所不同以外,其他各部分可按文中所述进行操作. Windows下正常使用ADB要注意以下问题:. 1.      手机端要打开调试模式.

大数据排序或取重或去重相关问题

- - 学着站在巨人的肩膀上
给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url. 方案1:可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G. 所以不可能将其完全加载到内存中处理. s 遍历文件a,对每个url求取 ,然后根据所取得的值将url分别存储到1000个小文件(记为 )中.

Android WebView Touch事件及相关问题处理

- - CSDN博客推荐文章
如有转载,请声明出处: 时之沙:  http://blog.csdn.net/t12x3456. 继上一篇  Android WebView常见问题及解决方案汇总 中归纳了一些处理webview的常见问题,这次要说的是webview中的touch事件:. 有时候在开发中,我们需要对webview加入触摸事件的处理,比如加入滑动效果或者类似于阅读中的翻页效果,这时候我们就需要重写webview中的onTouch方法:.

机器学习及大数据相关面试的职责和面试问题

- - IT瘾-bigdata
· 机器学习、大数据相关岗位的职责. 各个企业对这类岗位的命名可能有所不同,比如推荐算法/数据挖掘/自然语言处理/机器学习算法工程师,或简称算法工程师,还有的称为搜索/推荐算法工程师,甚至有的并入后台工程师的范畴,视岗位具体要求而定. 机器学习、大数据相关岗位的职责. 根据业务的不同,岗位职责大概分为:.

就是要你懂DNS--一文搞懂域名解析相关问题 | plantegg

- -
一文搞懂域名解析DNS相关问题. 本文希望通过一篇文章解决所有域名解析中相关的问题. 最后会通过实际工作中碰到的不同场景下几个DNS问题的分析过程来理解DNS. 一批ECS nslookup 域名结果正确,但是 ping 域名 返回 unknown host. Docker容器中的域名解析过程和原理.