成都传智播客吧 关注:267贴子:2,257
  • 3回复贴,共1

【成都校区*精品】Java实现二分查找

只看楼主收藏回复

查找二字,我们可以理解成:在大量的信息中寻找一个特定的信息元素。在计算机应用中,查找是非常常用的基本运算。在查找算法中,二分查找是一种效率较高并且实现起来较为简单的查找方法,本文将详细介绍用Java实现的二分查找。那么究竟什么是二分查找,我们又该如何实现二分查找呢,且听我细细道来。1. 先来看看顺序查找
1.1 猜数字游戏
如果现在随机选取一个1到10的数字藏在盒子里,现在让你猜盒子里的数字是什么,最简单的办法是什么?
其实最简单的办法就是从1开始一直猜到10,肯定有一个能猜对。
如果运气好,盒子里数字是1,那么一次就猜对了,但是如果运气特别差,盒子里数字是10,那么就需要猜十次。
上述找一个数字从头查找到末尾的方法,我们可以看做是顺序查找。我们先用ava代码来实现这种查找。
1.2 顺序查找实现
例如我们要完成以下需求:
要求在一个存储了多个整数的数组中查找指定元素所在的索引值
示范代码如下:


1楼2018-10-15 14:42回复


    2楼2018-10-15 14:43
    回复
      1.3 小总结
      优点:代码实现起来非常简单。
      缺点:效率低。最坏的情况,需要n+1次比较,顺序查找的时间复杂度为O(n)。接下来就来聊我们今天的主角:二分查找。
      2. 二分查找思想
      2.1 由猜数字游戏联想二分查找
      上述案例我们已经总结了顺序查找的缺点:效率低。那么相对来说效率比较高的二分查找又是怎么实现的呢?
      我们还是以猜数字游戏为例,在之前的猜数字游戏中,如果我们第一次猜 1 到 10 最中间的值:5,并且能知道5是偏大还是偏小,那么我们下一次猜就直接猜正确的那一半就行了,以此类推,每次排除一半错误的值,那么就能比较快定位到正确值了。
      1 2 3 4 <font color='red'>5</font> 6 7 8 9 10 如果第一次猜的数字是5,并且能被告知5这个值是偏大还是偏小,就能排除一半错误答案。
      为了能达到这个效果,那么这组数据必须是有序的
      二分查找也被称为折半查找,顾名思义就是在找元素的时候,每次都从最中间开始选取,如果选取最中间的元素后能确定要查找的元素是在相对于此元素的左边还是右边,那么就直接排除了一半的元素。


      2.2 二分查找的前提条件
      试想一下,如果上述案例中要猜的数据分布是没有大小顺序的,那么即使取中间的数据,告知中间数据和正确数据的大小关系,我们也没法定位正确数据在左半边还是右半边。
      6 4 8 2 <font color='red'>3</font> 10 7 5 9 1假设要猜的数字是8,我们第一次猜了中间的数字3,但是如果数组不是有序的,就没法定位8到底在左半边还是右半边。
      所以,必须保证被查找的数据是按顺序排列的,我们才能实现二分查找。


      2.3 小总结
      思想总结:二分查找就是用被查找数组中间的元素和要查找元素进行比较,每次都排除没有正确元素的那一半数组,直到查找到正确元素为止
      前提条件:进行二分查找的数组必须是有序的
      3. Java语言二分查找代码实现
      了解了实现思想后,我们就直接改写顺序查找算法,用二分查找思想来实现查找示范代码如下:


      3楼2018-10-15 14:43
      回复

        控制台输出:
        index:4


        4楼2018-10-15 14:46
        回复