首页 > 其他 > 详细

二分法查找

时间:2014-07-22 22:37:03      阅读:304      评论:0      收藏:0      [点我收藏+]

题设:设数组a[0],…,a[n-1]中存放着n>=1个已由小到大排序的不同整数,判断整数x是否在数组a中。若是,返回j,使得x=a[j];否则,返回-1。


题解:利用数组中的整数已排序的性质,可以设计高效的求解算法。令left和right分别表示当前需要查找的数组部分的起点与终点下标。
初始时,left=0,right=n-1.令middle=[(left+right)/2]为中点下标。比较a[middle]和x,有如下三种可能:
     ①x<a[middle] 这时,若x存在,则x的下标一定在left~middle-1之间,因此,将right设置成middle-1.
     ②x==a[middle] 这时,返回middle 即可。
     ③x>a[middle] 这时,若x存在,则x的下标一定在middle+1~right之间,因此将left设置成middle+1.
如果x还未找到且数组a中还有可供查找的整数,则可以通过循环重新计算middle,继续查找。该算法包含两个子任务:
    ①判断是否还有可供查找的整数,这可转化为判断是否left<=right
    ②比较x和a[middle],为了清晰描述整体算法,可用下面给出的compare函数实现。

1 char compare(int x,int y)
2 {
3     if (x>y)  return >;
4     else if (x<y)  return <;
5     else  return =;
6 }


得到二分查找函数

 1 int BinarySearch(int *a,const int x,const int n)
 2 {
 3     for(int left=0,int right =n-1;left<=right;)
 4     {
 5         int middle=(left+right)/2;
 6         switch(conpare(x,a[middle]))
 7         {
 8             case > :left=middle+1; break;
 9         }
10     }
11 }

 

当left+right 为奇数时,每经过一次循环比较,新的查找范围为原来一半或一半-1;
当left+right 为偶数时,每经过一次循环比较,新的查找范围为原来的一半-1;

二分法查找,布布扣,bubuko.com

二分法查找

原文:http://www.cnblogs.com/Ranbai-Selinda/p/3860747.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!