乐视2017暑假实习生笔试题二分查找之JAVA实现

试题

对一个含有20个元素的有序数组做二分查找,数组起始下标为1,则查找A[2]的比较序列的下标为()

A. 9,5,4,2 B. 10, 5, 3, 2 C. 9, 6, 2 D. 20, 10, 5, 3, 2

解析

没错,可能懂的人一眼就瞧出来了,选B;不懂的百度也能搜出来。当然网上也有不同的声音,有些童鞋感觉答案不对,在求指教!计算得出的是{10,5,2}。

吓得我赶紧百度了一下百度百科(尽管有时候也挺扯淡的),百度百科给出的demo是:

假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2. 1.开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为mid>x,故应在前半段中查找。 2.令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>mid,故确定应在后半段中查找。 3.令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a[mid]=x,查找成功。 如果要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。


如果按照案例,这位童鞋貌似算的不差也。然而他可能忽略了整数溢出的问题。

举个例子,比如 int型数据,JAVA里除号是下取整的。二分法,你mid有不断增加的可能,加法就容易溢出,超过int型数据的表达范围。

比如计算2个32位的数字,加法结果为64位,但是制定了数据类型为32位,结果就只能读这个64位数的低32位,这就是溢出。

有可能二分查找到数组的最后两个,如果数组的长度非常大,就有可能溢出。如果你要在数量为十亿级别数据库中查找,就要考虑这个溢出。

所以最好使用公式 int mid= (end- front) / 2 + front,看来百度百科也不大靠谱哈。

代码实现

package com.itstyle.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找  有则返回下标,无则返回-1
 */
public class Dichotomy {
    public static void main(String[] args) {
           int[] A = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
           binary(A,3);
       }
       public static int binary(int[] arr, int key) {
           List<String> numList = new ArrayList<String>();
           int start = 0;
           int end = arr.length - 1;
           while (start <= end) {
               int middle = (end - start) / 2+1;
               //int middle = (start + end);//2+1;若使用(start + end)/2求中间位置容易溢出
               numList.add(middle+"");
               if (key < arr[middle]) {
                   end = middle - 1;
               } else if (key > arr[middle]) {
                   start = middle + 1;
               } else {
                   System.out.println("A[2]下标为:"+numList);
                   return middle;
               }
           }
           return -1;
       }
}

输出结果是 A[2]下标为:[10, 5, 3, 2],因为JAVA中数组的下标是从0开始的,所以输入的binary(A,3)是3。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

《笨办法学Python》 第24课手记

《笨办法学Python》 第24课手记 本节课是前面所有课程的复习,请认真对待,也许你都理解这些代码的含义,那么请尽量努力一次通过,不要出现任何错误。如果你出现...

2009
来自专栏java一日一条

Java IAQ:很少被回答的问题

一个问题如果被回答地很少,有可能是因为知道答案的人很少,亦或是因为问题本身模糊不清、微不足道(但对你来讲可能很关键)。我似乎发明了一个术语,但是它在一个信息量很...

1042
来自专栏青蛙要fly的专栏

Android技能树 — 排序算法基础小结

现在安卓面试,对于算法的问题也越来越多了,要求也越来越多,特别是排序,基本必考题,而且还动不动就要手写,所以陆续要写算法的文章,也正好当自己学习。o(╥﹏╥)o

872
来自专栏Play & Scala 技术分享

挑逗 Java 程序员的那些 Scala 绝技

有个问题一直困扰着 Scala 社区,为什么一些 Java 开发者将 Scala 捧到了天上,认为它是来自上帝之吻的完美语言;而另外一些 Java 开发者却对它...

1766
来自专栏zingpLiu

python基础(一)

  python的创始人为吉多·范罗苏姆(Guido van Rossum)。1989年的圣诞节期间,吉多·范罗苏姆为了在阿姆斯特丹打发时间,决心开发一个新的脚...

2512
来自专栏xingoo, 一个梦想做发明家的程序员

《JavaScript语言精粹》—— 读书总结

话说这本书还是同学的推荐才读的,之前感觉这本书太薄了,不值得看,没想到小身材有大智慧,书中的内容总结的还是很到位的!所以就把最后几章,精华的部分整理整理。 优...

2779
来自专栏C语言及其他语言

[每日一题]字符串的连接

上一次是要反序输出字符串,而这次是要连接两个字符串,难度都不大,快来试试吧! 题目描述 写一函数,将两个字符串连接 输入 两行字符串 输出 链接后的字符串 样...

3166
来自专栏Java面试通关手册

深入理解工厂模式

Java面试通关手册(Java学习指南,欢迎Star,会一直完善下去,欢迎建议和指导):https://github.com/Snailclimb/Java_G...

28813
来自专栏北京马哥教育

深入 Python 字典的内部实现

字典是通过键(key)索引的,因此,字典也可视作彼此关联的两个数组。下面我们尝试向字典中添加3个键/值(key/value)对: 这些值可通过如下方法访问: 由...

38515
来自专栏java学习

Java每日一练(2017/7/18)

新通知 ●回复"每日一练"获取以前的题目! ●【新】Ajax知识点视频更新了!(回复【学习视频】获取下载链接) ●【新】HTML5知识点视频更新了!(回复【前端...

35610

扫码关注云+社区

领取腾讯云代金券