Java实现二分查找

【传智播客.黑马程序员训练营成都中心】

转载请注明出处
作者: 成都校区.堂堂老师

前言

查找二字，我们可以理解成：在大量的信息中寻找一个特定的信息元素。在计算机应用中，查找是非常常用的基本运算。在查找算法中，二分查找是一种效率较高并且实现起来较为简单的查找方法，本文将详细介绍用Java实现的二分查找。那么究竟什么是二分查找，我们又该如何实现二分查找呢，且听我细细道来。

1. 先来看看顺序查找

1.1 猜数字游戏
- 如果现在随机选取一个1到10的数字藏在盒子里，现在让你猜盒子里的数字是什么，最简单的办法是什么？
- 其实最简单的办法就是从1开始一直猜到10，肯定有一个能猜对。
- 如果运气好，盒子里数字是1，那么一次就猜对了，但是如果运气特别差，盒子里数字是10，那么就需要猜十次。
上述找一个数字从头查找到末尾的方法，我们可以看做是顺序查找。我们先用ava代码来实现这种查找。

1.2 顺序查找实现

例如我们要完成以下需求：

要求在一个存储了多个整数的数组中查找指定元素所在的索引值

示范代码如下：

public class Test {
  public static void main(String[] args) {
      //准备好被查找的数组
      int[] arr = { 2, 3, 5, 1, 6, 4, 9, 7, 8 }; 
      //调用查找方法查找给定数组中5元素所在的索引值，并接收查找到的索引
      int index = getIndex(arr, 5);
      //输出索引
      System.out.println("index:"+index);
  }

  public static int getIndex(int[] arr, int num) {
      for (int i = 0; i < arr.length; i++) {
          //按顺序遍历获取数组中的每个元素和要查找的元素进行比较
          if (num == arr[i]) {
              //如果要查找的元素值等于对应位置的元素值，则返回索引
              return i;
          }
      }
      //如果所有的元素都不等于要查找的元素，则返回-1表示没有找到
      return -1;
  }
}

控制台输出：

index:2

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语言二分查找代码实现

了解了实现思想后，我们就直接改写顺序查找算法，用二分查找思想来实现查找

示范代码如下：

public class Test {
  public static void main(String[] args) {
      // 准备好一个有序的被查找数组
      int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
      // 调用查找方法查找给定数组中5元素所在的索引值，并接收查找到的索引
      int index = getIndex(arr, 5);
      // 输出索引
      System.out.println("index:" + index);
  }

  public static int getIndex(int[] arr, int num) {
      // 定义变量，表示查找数组范围的最左侧，先从0索引开始
      int left = 0; 
      // 定义变量，表示查找数组范围的最右侧，先从最大索引开始
      int right = arr.length - 1;
      // 定义变量，表示查找范围的中间值
      int mid;
      while (left <= right) {
          // 中间索引 = (左侧  + 右侧) / 2
          // mid = (left + right) / 2; 
          // 为了提高效率，我们可以用位运算代替除以运算
          mid = (left + right) >>> 2 
          if (arr[mid] > num) {
              //如果中间元素大于要查找元素，则在中间元素的左侧去找正确元素，最右侧变为mid - 1
              right = mid - 1;
          } else if (arr[mid] < num) {
              //如果中间元素小于要查找元素，则在中间元素的右侧去找正确元素，最左侧变为mid + 1
              left = mid + 1;
          } else {
              // 如果不大不小，那么就正好是找到了，返回找到的索引
              return mid;
          }
      }
      // 当查找范围的最左侧和最右侧重叠后还没有找到元素，则返回-1表示没有找到
      return -1;
  }
}

控制台输出：

index:4

总结

到目前为止我们已经用Java实现了二分查找。二分查找是一种相对简单而且比较高效的查找算法了，它的局限性就是被查找的数据需要有序。那么对其他查找算法感兴趣的小伙伴还可以去自行了解哈希查找，斐波那契查找等。好了，以上就是本文的全部内容，感谢观看。