专栏首页用户2442861的专栏C/C++ 笔试面试(2)——二分查找

C/C++ 笔试面试(2)——二分查找

转载于 http://blog.csdn.net/yangtrees/article/details/8898997

Bentley在他的著作《Writing Correct Programs》中写道,90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。

难怪有人说,二分查找原理简单,甚至小学生都能明白。不过这查找算法好多专家都写不好。我自己尝试了一下,确实要第一次就完全写正确不容易.以下两份实现依次为迭代和递归版本的代码,二分查找的思想很多人都清楚,但是这里有一个细节就是要注意边界的选择。

[cpp] view plaincopyprint?

 //迭代方法 
 int search(int array[], int n, int v)  
 {  
  int left, right, middle;  
  
     left = 0, right = n - 1;  
  
  while (left <= right)  
     {  
         middle = (left + right) / 2;  
  if (array[middle] > v)  
         {  
             right = middle - 1;  
         }  
  else if (array[middle] < v)  
         {  
             left = middle + 1;  
         }  
  else 
         {  
  return middle;  
         }  
     }  
  
  return -1;  
 }  
 //递归方法 
 int search_recurse(int array[], int low, int high, int v)  
 {  
  int middle;  
  
     middle = (low + high) / 2;  
  
  if (low < high)  
     {  
  if (array[middle] > v)  
         {  
  return search_recurse(array, low, middle, v);  
         }  
  else if (array[middle] < v)  
         {  
  return search_recurse(array, middle + 1, high, v);  
         }  
  else 
         {  
  return middle;  
         }  
     }  
  else if (low == high)  
     {  
  if (array[middle] == v)  
         {  
  return middle;  
         }  
  else 
         {  
  return -1;  
         }  
  
     }  
  else 
     {  
  return -1;  
     }  
  
  return -1;  
 }  
  
 int main()  
 {  
  int array[] = {0, 1, 2, 3, 4, 5, 6, 7, 13, 19};  
  
  int m = search(array, sizeof(array)/sizeof(array[0]), 13);  
  
     printf("m = %d\n", m);  
  
     m = search_recurse(array, 0, sizeof(array)/sizeof(array[0]), 13);  
  
     printf("m = %d\n", m);  
  
  return 0;  
 }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 百度笔试题目

    http://blog.csdn.net/liuzhanchen1987/article/details/7987985

    bear_fish
  • java获取指定文件夹下的所有文件名

    http://blog.csdn.net/tomorrowzm/article/details/3693653

    bear_fish
  • Python之逻辑运算和缩进和选择if

    作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

    bear_fish
  • python 预测目标(y)的转换

    LabelEncoder是一个可以用来将标签规范化的工具类,它可以将标签的编码值范围限定在[0,n_classes-1]。这在编写高效的Cython程序时是非常...

    用户1359560
  • Metinfo 6.0.0 后台getshell 漏洞分析 CVE-2018-13024

    最近看代码看的头疼,主要是想通过代码审计来提高自己对一些cms模块设计的理解,然后提高自己阅读代码的速度。 只是菜?一个,大牛不要喷我。 metinfo 6.0...

    用户5878089
  • Python基础----数据变量和变量

    整数 Python可以处理任意大小的整数,当然包括负整数,在程序中的表示方法和数学上的写法一模一样,例如:1,100,-8080,0,等等。 计算机由于使用...

    GavinZhou
  • 思科收购July Systems以支持Wi-Fi应用

    思科19日表示,它打算收购移动公司July Systems,以使用室内定位服务提升企业WiFi平台,该交易的条款尚未披露。

    SDNLAB
  • 大数据项目产品选型的五个建议

    原创作者:曾勇,Elastic工程师。 数据如今对企业来说可谓是头等大事。使用欺诈检测来降低财务风险或是建设推荐系统来改善用户体验,都需要数据来为企业解决这些日...

    iCDO互联网数据官
  • Python模块的交叉引用(导入循环)问题分析

        首先交叉引用或是相互引用,实际上就是导入循环,关于导入循环的详细说明,可见我摘自《python核心编程》第二版的摘抄:Python导入循环方法。

    党志强
  • 也谈“精益”|洞见

    精益对大家来说都不陌生了,无论是最开始提取的丰田制造原型,还是后面延伸出来的物流供应链管理,再到近两年颇为流行的精益创业(Lean Startup),都在不停刷...

    ThoughtWorks

扫码关注云+社区

领取腾讯云代金券