二分搜索的基本相关问题

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

如何使用机器学习解决实际问题-以关键词相关性模型为例

- - Dustinsea
本文以百度关键词搜索推荐工具字面相关性模型为基础,介绍一个机器学习任务的具体设计实现. 包括目标的设定,训练数据准备,特征选择及筛选, 以及模型的训练及优化. 该模型可扩展到语意相关性模型,搜索引擎相关性及LTR学习任务的设计实现. 目标设定:提升关键词搜索相关性. 作为一个搜索+推荐产品,百度关键词搜索推荐系统的产品形态是向凤巢用户推荐适合他业务的关键词.