二分查找法的实现和应用汇总

标签: 二分查找 应用 | 发表时间:2012-09-11 08:00 | 作者:[email protected] (秩名)
出处:http://www.kuqin.com/jingyan/

在学习算法的过程中,我们除了要了解某个算法的基本原理、实现方式,更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间,我们又会更注重时间复杂度。

时间复杂度按优劣排差不多集中在:

O(1), O(log n), O(n), O(n log n), O(n 2), O(n k), O(2 n)

到目前位置,似乎我学到的算法中,时间复杂度是O(log n),好像就数二分查找法,其他的诸如排序算法都是 O(n log n)或者O(n 2)。但是也正是因为有二分的 O(log n), 才让很多 O(n 2)缩减到只要O(n log n)。

二分查找法主要是解决在“一堆数中找出指定的数”这类问题。

而想要应用二分查找法,这“一堆数”必须有一下特征:

  • 存储在数组中
  • 有序排列

所以如果是用链表存储的,就无法在其上应用二分查找法了。(�诿媸员晃识植檎曳ǹ梢允裁词萁峁股鲜褂茫菏椋苛幢恚浚�/p>

至于是顺序递增排列还是递减排列,数组中是否存在相同的元素都不要紧。不过一般情况,我们还是希望并假设数组是递增排列,数组中的元素互不相同。

二分查找法的基本实现

二分查找法在算法家族大类中属于“分治法”,分治法基本都可以用递归来实现的,二分查找法的递归实现如下:

复制代码

int bsearch(int array[], int low, int high, int target)        
{
if (low > high) return -1;

int mid = (low + high)/2;
if (array[mid]> target)
return binarysearch(array, low, mid -1, target);
if (array[mid]< target)
return binarysearch(array, mid+1, high, target);

//if (midValue == target)
return mid;
}

复制代码

不过所有的递归都可以自行定义stack来解递归,所以二分查找法也可以不用递归实现,而且它的非递归实现甚至可以不用栈,因为二分的递归其实是尾递归,它不关心递归前的所有信息。

复制代码

int bsearchWithoutRecursion(int array[], int low, int high, int target)        
{
while(low <= high)
{
int mid = (low + high)/2;
if (array[mid] > target)
high = mid - 1;
else if (array[mid] < target)
low = mid + 1;
else //find the target
return mid;
}
//the array does not contain the target
return -1;
}

复制代码

只用小于比较(<)实现二分查找法

在前面的二分查找实现中,我们既用到了小于比较(<)也用到了大于比较(>),也可能还需要相等比较(==)。

而实际上我们只需要一个小于比较(<)就可以。因为错逻辑上讲a>b和b<a应该是有相当的逻辑值;而a==b则是等价于 !((a<b)||(b<a)),也就是说a既不小于b,也不大于b。

当然在程序的世界里, 这种关系逻辑其实并不是完全正确。另外,C++还允许对对象进行运算符的重载,因此开发人员完全可以随意设计和实现这些关系运算符的逻辑值。

不过在整型数据面前,这些关系运算符之间的逻辑关系还是成立的,而且在开发过程中,我们还是会遵循这些逻辑等价关系来重载关系运算符。

干嘛要搞得那么羞涩,只用一个关系运算符呢?因为这样可以为二分查找法写一个template,又能减少对目标对象的要求。模板会是这样的:

复制代码

template <typename T, typename V>        
inline int BSearch(T& array, int low, int high, V& target)
{
while(!(high < low))
{
int mid = (low + high)/2;
if (target < array[mid])
high = mid - 1;
else if (array[mid] < target)
low = mid + 1;
else //find the target
return mid;
}
//the array does not contain the target
return -1;
}

复制代码

我们只需要求target的类型V有重载小于运算符就可以。而对于V的集合类型T,则需要有[]运算符的重载。当然其内部实现必须是O(1)的复杂度,否则也就失去了二分查找的效率。

用二分查找法找寻边界值

之前的都是在数组中找到一个数要与目标相等,如果不存在则返回-1。我们也可以用二分查找法找寻边界值,也就是说在 有序数组中找到“正好大于(小于)目标数”的那个数。

用数学的表述方式就是:

在集合中找到一个大于(小于)目标数t的数x,使得集合中的任意数要么大于(小于)等于x,要么小于(大于)等于t。

举例来说:

给予数组和目标数

int array = {2, 3, 5, 7, 11, 13, 17};        
int target = 7;

那么上界值应该是11,因为它“刚刚好”大于7;下届值则是5,因为它“刚刚好”小于7。

用二分查找法找寻上届

复制代码

//Find the fisrt element, whose value is larger than target, in a sorted array         
int BSearchUpperBound(int array[], int low, int high, int target)
{
//Array is empty or target is larger than any every element in array
if(low > high || target >= array[high]) return -1;

int mid = (low + high) / 2;
while (high > low)
{
if (array[mid] > target)
high = mid;
else
low = mid + 1;

mid = (low + high) / 2;
}

return mid;
}

复制代码

与精确查找不同之处在于,精确查找分成三类: 大于小于等于(目标数)。而界限查找则分成了两类: 大于不大于

如果当前找到的数大于目标数时,它可能就是我们要找的数,所以需要保留这个索引,也因此if (array[mid] > target)时 high=mid; 而没有减1。

用二分查找法找寻下届

复制代码

//Find the last element, whose value is less than target, in a sorted array         
int BSearchLowerBound(int array[], int low, int high, int target)
{
//Array is empty or target is less than any every element in array
if(high < low || target <= array[low]) return -1;

int mid = (low + high + 1) / 2; //make mid lean to large side
while (low < high)
{
if (array[mid] < target)
low = mid;
else
high = mid - 1;

mid = (low + high + 1) / 2;
}

return mid;
}

复制代码

下届寻找基本与上届相同,需要注意的是在取中间索引时,使用了向上取整。若同之前一样使用向下取整,那么当low == high-1,而array[low] 又小于 target时就会形成死循环。因为low无法往上爬超过high。

这两个实现都是找 严格界限,也就是要大于或者小于。如果要找松散界限,也就是找到大于等于或者小于等于的值(即包含自身),只要对代码稍作修改就好了:

去掉判断数组边界的等号:

target >= array[high]改为 target > array[high]

在与中间值的比较中加上等号:

array[mid] > target改为array[mid] >= target

用二分查找法找寻区域

之前我们使用二分查找法时,都是基于 数组中的元素各不相同。假如存在重复数据,而数组依然有序,那么我们还是可以用二分查找法判别目标数是否存在。不过,返回的index就只能是随机的重复数据中的某一个。

此时,我们会希望知道有多少个目标数存在。或者说我们希望数组的区域。

结合前面的界限查找,我们只要找到目标数的严格上届和严格下届,那么界限之间(不包括界限)的数据就是目标数的区域了。

复制代码

//return type: pair<int, int>        
//the fisrt value indicate the begining of range,
//the second value indicate the end of range.
//If target is not find, (-1,-1) will be returned
pair<int, int> SearchRange(int A[], int n, int target)
{
pair<int, int> r(-1, -1);
if (n <= 0) return r;

int lower = BSearchLowerBound(A, 0, n-1, target);
lower = lower + 1; //move to next element

if(A[lower] == target)
r.first = lower;
else //target is not in the array
return r;

int upper = BSearchUpperBound(A, 0, n-1, target);
upper = upper < 0? (n-1):(upper - 1); //move to previous element

//since in previous search we had check whether the target is
//in the array or not, we do not need to check it here again
r.second = upper;

return r;
}

复制代码

它的时间复杂度是两次二分查找所用时间的和,也就是O(log n) + O(log n),最后还是O(log n)。

在轮转后的有序数组上应用二分查找法

之前我们说过二分法是要应用在 有序的数组上,如果是无序的,那么比较和二分就没有意义了。

不过还有一种特殊的数组上也同样可以应用,那就是“轮转后的有序数组(Rotated Sorted Array)”。它是有序数组,取期中某一个数为轴,将其之前的所有数都轮转到数组的末尾所得。比如{7, 11, 13, 17, 2, 3, 5}就是一个轮转后的有序数组。非严格意义上讲,有序数组也属于轮转后的有序数组——我们取首元素作为轴进行轮转。

下边就是二分查找法在轮转后的有序数组上的实现(假设数组中不存在相同的元素)

复制代码

int SearchInRotatedSortedArray(int array[], int low, int high, int target)         
{
while(low <= high)
{
int mid = (low + high) / 2;
if (target < array[mid])
if (array[mid] < array[high])//the higher part is sorted
high = mid - 1; //the target would only be in lower part
else //the lower part is sorted
if(target < array[low])//the target is less than all elements in low part
low = mid + 1;
else
high = mid - 1;

else if(array[mid] < target)
if (array[low] < array[mid])// the lower part is sorted
low = mid + 1; //the target would only be in higher part
else //the higher part is sorted
if (array[high] < target)//the target is larger than all elements in higher part
high = mid - 1;
else
low = mid + 1;
else //if(array[mid] == target)
return mid;
}

return -1;
}

复制代码

对比普通的二分查找法,为了确定目标数会落在二分后的那个部分,我们需要更多的判定条件。但是我们还是实现了O(log n)的目标。

二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上:

必须有序,我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序,可是又落到了第二个瓶颈上:它必须是数组。

数组读取效率是O(1),可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。

解决这些缺陷问题更好的方法应该是使用二叉查找树了,最好自然是自平衡二叉查找树了,自能高效的(O(n log n))构建有序元素集合,又能如同二分查找法一样快速(O(log n))的搜寻目标数。

正在加载推荐文章
Buzz应用场景汇总&畅想
最详尽的iOS文本编辑器应用对比汇总
18则你不知道的QQ应用技巧汇总
Twitter第三方应用汇总
  • 默认表情
  • 阿狸
发  布
  或游客留言 社会化登录:
  • 默认表情
  • 阿狸
回  复
  或游客留言 社会化登录:
www.kuqin.com
数据正在加载中...
无觅相关文章插件,快速提升流量

[ comments ]

相关 [二分查找 应用] 推荐:

二分查找法的实现和应用汇总

- - 酷勤网-挖经验 [expanded by feedex.net]
在学习算法的过程中,我们除了要了解某个算法的基本原理、实现方式,更重要的一个环节是利用big-O理论来分析算法的复杂度. 在时间复杂度和空间复杂度之间,我们又会更注重时间复杂度. 时间复杂度按优劣排差不多集中在:. 到目前位置,似乎我学到的算法中,时间复杂度是O(log n),好像就数二分查找法,其他的诸如排序算法都是 O(n log n)或者O(n.

比普通二分查找快4倍的结构

- GLORY - 构架师-搜索引擎-冲出宇宙(健健康康:http://www.zhaojk.com)
 二分查找是查询有序数组的有效结构,对于规模为N的有序数组来说,二分查找算法的时间复杂度为O(logN).  即每次选择数组范围的中间数据和查询数据比较,如果不等于查询数据则选择一半的范围继续查询.  算法每次选择一段范围的中间节点,每次都相当于一个随机位置比较,对cache和磁盘等非随机结构很不友好.

二分查找(Binary Search)需要注意的问题,以及在数据库内核中的实现

- - OurMySQL
今年的实习生招聘考试,我出了一道二分查找(Binary Search)的题目. 给定一个升序排列的自然数数组,数组中包含重复数字,例如:[1,2,2,3,4,4,4,5,6,7,7]. 问题:给定任意自然数,对数组进行二分查找,返回数组正确的位置,给出函数实现. 注:连续相同的数字,返回第一个匹配位置还是最后一个匹配位置,由函数传入参数决定.

GetEd2k (Android应用)

- 某牢 - eMule Fans 电骡爱好者
GetEd2k是一个Android应用程序,作者是anacletus. 此应用可以帮助你把网页中的电驴(eDonkey) 链接添加到你个人电脑的电驴客户端里,不过前提是你的客户端开启了用于远程控制的Web interface(Web服务器,网页接口,Web界面),当然,eMule(电骡), MLDonkey 和 aMule 都支持该功能,所以这三种主流电驴客户端的用户都可以使用GetEd2k.

fixed应用

- - ITeye博客
今天在逛人人网时,发现人人网首页左侧的“应用动态”,随着我页面向下滚动,一直固定在网站的左侧. 但这效果存在一点瑕疵,在拖动过程中存在一点抖动(ie下),不是非常平滑. 我尝试使用jquey实现了该效果,也解决了抖动的问题. 创建一个ID为sideBar的div,将它的position设置为absolute.

Voldemort应用

- - 冰火岛
    互联网数据应用产品涉及到到大数据存储,譬如推荐系统,精准营销,个性化搜索这样的产品,后台离线计算的海量数据需要展示给用户. 在电子商务应用中,譬如将User作为key,给用户挖掘的结果作为value;或者以商品id作为key,商品挖掘的知识作为value,这些数据可以通过KV存储,从而满足实际需求.

httpclient4的应用

- - 编程语言 - ITeye博客
httpclient一个实现了HTTP协议的客户端编程工具包. 一个使用的背景:登录需要验证,需要压力测试一下,用webdriver等工具搞不定. 就用到了他,有ocr开源的工具,结合httpclient完美的处理了. 网上的例子主要是3的版本,这里主要是总结一下4的版本. 本身带的例子也不错:下载地址,api的参考.

Solr SpellCheck 应用

- - 开源软件 - ITeye博客
通过对各类型的SpellCheck组件学习,完成项目拼写检查功能. 本文使用基于拼写词典的实现方式,solr版本为5.3.0. SpellCheck 简述. 拼写检查是对用户错误输入,响应正确的检查建议. 比如输入:周杰轮,响应:你是不是想找 周杰伦. Solr的拼写检查大致可分为两类,基于词典与基于Solr索引.

当应用不仅仅是应用

- HACK21 - 爱范儿 · Beats of Bits
(Ankit Gupta 和 Akshay Kothari 是 Pulse 的创始人,他们的应用在 iOS/Android 平台获得极高的下载量,曾获得乔布斯的赞赏. 他们的公司 Alphonso Labs 获得了 100 万风投和天使投资). by  ankit gupta from posterous blog |  积木 译,转载请注明 ifanr 译文链接.

JMS - JMS​应​用​领​域 应用场景

- - 企业架构 - ITeye博客
Java的JMS消息类型有文本类型,对象类型,字节类型,流类型,XML类型,实际项目中,用的最多的是文本类型,对象类型和xml类型的消息.建议最好不用对象类型,因为如果用对象类型的话,调试的时候是很麻烦的,. 首先你必须要写专门的测试代码用来发送消息,. 第二,必须要管理对象所属的类的不同版本,. 第三,不方便查看queue或者topic中的消息内容..