先给大家贴个题,热乎的,最新的阿里2014实习生笔试题(2014.3.29)。
很经典的二分查找,找出其中的bug。
题目让指出bug,我想应该是具体的说明错在哪,怎么错了。
应该是有两处bug:
1) while 循环处条件有错,如果只有一个元素,则返回的肯定的-1,导致答案错误。应改为 end >= start
2) 程序会进入死循环。考虑 start =1, end= 2. 假设 middle = 1. 若每次都执行 start=midlle, 即进入死循环。应改为 start = middle+1; end = middle-1;
另外,本题没有说已排序的数组是递增还是递减的。我在答题时又考虑了递减的情况,不算多余吧。
顺便给下完整的代码:
03 |
int binarySearch( int arr[], int l, int r, int x)
|
09 |
if (arr[m] == x) return m;
|
11 |
if (arr[m] < x) l = m + 1;
|
20 |
int arr[] = {2, 3, 4, 10, 40};
|
21 |
int n = sizeof (arr)/ sizeof (arr[0]);
|
23 |
int result = binarySearch(arr, 0, n-1, x);
|
24 |
(result == -1)? printf ( "Element is not present in array" )
|
25 |
: printf ( "Element is present at index %d" , result);
|
递归的实现:
01 |
int binarySearch( int arr[], int l, int r, int x)
|
05 |
int mid = l + (r - l)/2;
|
06 |
if (arr[mid] == x) return mid;
|
07 |
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
|
08 |
return binarySearch(arr, mid+1, r, x);
|
更多关于二分的问题请看无处不在的二分查找
分享到:
相关推荐
,只有将正确结果14输入才能通过验证,超级安全,经典实用,执行速度超快,纯数字显示,不必担心验证码无法显示; 38、阿赛文件上传系统商业版:再次升级上传系统,支持各种文件的在线上传,上传后可进行打开预览,...
能使用二分法查找的线性表必须满足用顺序存储结构和线性表是有序表两个条件。 “有序”是特指元素按非递减排列,即从小到大排列,但允许相邻元素相等。下一节排序中,有序的含义也是如此。 对于长度为n的有序线性表...
1.在有序表A[1..18]中,采用二分查找算法查找元素值等于A[7]的元素,所比较过的元素的下标依次为 。 2.利用逐点插入法建立序列(61,75,44,99,77,30,36,45)对应的二叉排序树以后,查找元素36要进行 次元素间...
代码的位置必须在物理内存中才能被运行,由于现在的操作系统中有非常多的程序运行着,内存中不能够完全放下,所以引出了虚拟内存的概念。把哪些不常用的程序片断就放入虚拟内存,当需要用到它的时候在load入主存...
作用之二,直接作为菜单的背景(即不加载图像背景)。此时只设置字体的前景色即可。 2.增加动画菜单。 splashimage --animated=[type]=[delay]=[last_num]=[x]=[y] START_FILE 类型[type]:bit 0-3: 播放次数 bit...
(2)能查找通讯录中某人的信息; (3)能添加和删除通讯录中的指定项。 注:要用面向对象的方法来设计程序,每个通讯录是一个类的实例; 3、从终端读入字符集大小为n(即字符的个数),逐一输入n个字符和...
修改BUG:在IDE中打开源代码文件(.e)后,高级选择夹组件不能正确切换到“现行子夹”属性设定的子夹。 9. 修改BUG:矢量动画支持库中的“矢量编辑框”组件在光标位于组件右下角时按右光标键进入下一行会导致显示...
-修正此函数通过PageContext.RegisterStartupScript调用时不能正确显示Icon的BUG(feedback:zhaowenke)。 -修正basic/hello.aspx示例在单独浏览器打开后,不能弹出对话框的BUG。 -隐藏示例首页最外层RegionPanel...
是否ATM方式与同步通信完全无关? 第3章 数据链路层 问题3-1:在1999年4月出版的《计算机网络》(第2版)的1.3.2节中有这样的话: “(2) 数据链路层 数据链路层的任务是在两个相邻结点间的线路上无差错地传送以帧...
在系统关机前使用 shutdown命令,系统管理员会通知所有登录的用户系统将要关闭,并且login指令会被冻结,即新的用户不能再登录。 halt 1.作用 halt命令的作用是关闭系统,它的使用权限是超级用户。 2.格式 halt...
捷方式了,它还实施了一条规约,那就是一个字符串各个分离的部分包含的是完全相同的字符.例如:下面的正则表达式匹配的就是位于单引号或双引号之内的所有字 符.但是,它要求开始和结束的引号匹配(例如两个都是双引号...
简明批处理教程22009年10月20日 星期二 下午 05:35 最近对于批处理技术的探讨比较热,也有不少好的批处理程序发布,但是如果没有一定的相关知识恐怕不容易看懂和理解这些批处理文件,也就更谈不上自己动手编写了,古...
你可以用小括号来指定子表达式(也叫做分组),然后你就可以指定这个子表达式的重复次数了,你也可以对子表达式进行其它一些操作(后面会有介绍)。 (\d{1,3}\.){3}\d{1,3}是一个简单的IP地址匹配表达式。要理解这个...
Excel2007图表完全剖析 6/8 Excel2007 图表 完全剖析 OFFICE2007 完整清晰版 PDF ,有目录。共 150MB,分为8个分卷 原价:45.00元 作者:杰莱 出版社:人民邮电出版社 出版日期:2008年2月1日 ISBN:9787115171955 ...
能进行二分查找的线性表,必须以16.下面的说法中正确的是 (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。 (2)按二叉树定义,具有三个节点的二叉树共有6种。17.以下与数据的存储结构无关的术语是
书中的各章都是相对独立的,因此,你不必担心意想不到的或不必要的各章之间的依赖关系。每一章都是以节为单位,内容由易到难。如果将本书用于本科生的课程,可以选用每一章的前面几节内容;在研究生课程中,则可以...
-修正此函数通过PageContext.RegisterStartupScript调用时不能正确显示Icon的BUG(feedback:zhaowenke)。 -修正basic/hello.aspx示例在单独浏览器打开后,不能弹出对话框的BUG。 -隐藏示例首页最外层RegionPanel...
这是一个典型的分支控制指令,该指令的作用完全类似于Java语言中的if,if指令的语法格式如下: <#if condition>... <#elseif condition>... <#elseif condition>... <#else> ... 例子如下: (age>60)>老年人 ...
Excel2007图表完全剖析 8/8 Excel2007 图表 完全剖析 OFFICE2007 完整清晰版 PDF ,有目录。共 150MB,分为8个分卷 原价:45.00元 作者:杰莱 出版社:人民邮电出版社 出版日期:2008年2月1日 ISBN:9787115171955 ...