二分查找算法学习总结_二分法最少需要几次公式

目录

1、前言​

2、算法描述

3、算法实现

3.1 代码

3.2 测试

3.3 小结

4、解决整数溢出问题

5、相关面试题

---

1、前言

  这里是一个数组，数组里面都是些不重复的数字， 那我现在想要数组里面有没有74这个数字，当然了，我们用肉眼很容易判断最后一个就是74这个数字，一下就可以找到了。

  但是计算机它没这么聪明，你让计算机去找这个数字的话，它得从头到尾去对比。

  比如我现在要找74这个数字，那计算机就要先看索引0是不是这个数字，不是就再看索引1，还不是，显然在我的这个例子中，计算机要比较32次才能找到74这个数字。

  那这个效率高不高呢?也还可以，比较32次就可以找到它，但是，如果我们的这个数组的元素个数特别的多，比如10000，怎么办，最糟糕情况下，你要找的元素正好也是最后一个，那就要比较10000次，这个效率是无法接受的。

  因此我们就要使用到本篇博客要介绍的二分查找算法来提高检索效率， 不过呢，二分查找它有个前提，就是我们要查找的这个数组必须是有序的。

 

2、算法描述

我们现在呢就找128这个数字

前提：

有已排序数组

 

定义左边界 L、右边界 R，确定搜索范围：

首先我们要确定一个搜索的范围，这个范围一开始就是从0到31。

 

确定了这个范围以后，我们不是一个一个比较，而是在它这个范围内，挑它中间的值进行比较。

 

那么它的中间值就是这个索引为15的74,那个这个74和我们要查找的128做一个比较，显然74是小于128的。

数组现在是排好序的，那74左边这些元素就比128小，既然74左边这些都比128小，就不需要再跟128比了。

 

这样就比我们原来要比较的次数减小了一半，接下来我们就只需要从74右边的这些元素中去找。  

我们在这个范围内再挑一个中间值111，跟128比，小，所以111左边这些也不需要再跟128比了。  

以此类推  

次我们找到了128这个数字。我们一共比较了3次。

注：如果我们的左边界 L > 右边界R 时，表示没有找到，应结束循环。

3、算法实现

3.1 代码

package com.jie.binary;
 
 
/**
 * @description:二分查找
 * @author: jie
 * @time: 2022/2/7 22:08
 */
public class binary {
    public static void main(String[] args) {
        //声明数组
        int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
        //要查找的元素
        int target = 48;
        //调用二分查找方法
        int idx = binarySearch(array, target);
        //打印
        System.out.println(idx);
    }
    /**
     * @description:二分查找，找到返回元素索引，找不到返回-1
     * @author: jie
     * @time: 2022/2/7 22:12
     */
    public static int binarySearch(int[] a,int t){
        //定义左边界l，右边界r,中间索引m
        int l = 0, r = a.length-1, m;
        //循环查找  条件l<=r说明左边界还没有超过右边界，这时候我们就不断循环查找。
        while(l <= r){
            //计算中间索引m
            m = (l + r) / 2;
            //如果a[m]==t说明相等，直接返回m
            if(a[m]==t){
                return m;
            //如果大于t，说明索引右边的都不需要比了
            }else if(a[m] > t){
                 //重新设置右边界
                r = m-1;
            //小于t，说明索引左边的都不需要比了
            }else{
                //重新设置左边界
                l = m+1;
            }
        }
        return -1;
    }
 
}

3.2 测试

有的元素：

没有的元素：  

3.3 小结

1. 前提：有已排序数组 A（假设已经做好）

2. 定义左边界 L、右边界 R，确定搜索范围，循环执行二分查找（3、4两步）

3. 获取中间索引 M = Floor((L+R) /2)

4. 中间索引的值 A[M] 与待搜索的值 T 进行比较

① A[M] == T 表示找到，返回中间索引

② A[M] > T，中间值右侧的其它元素都大于 T，无需比较，中间索引左边去找，M - 1 设置为右边界，重新查找

③ A[M] < T，中间值左侧的其它元素都小于 T，无需比较，中间索引右边去找， M + 1 设置为左边界，重新查找

1. 当 L > R 时，表示没有找到，应结束循环

4、解决整数溢出问题

二分查找代码已经演示完了，但是有一个细节我们要注意一下，就是在计算中间索引 M 的时候，我们用的L+R/2这个公式，但是当L和R取值都特别大的时候，它俩相加就有可能超过整数能存储的最大值，从而造成这个整数溢出问题。整数取值范围( -2147483648~2147483647 )

package com.jie.binary;
/**
 * @description:整数溢出
 * @author: jie
 * @time: 2022/2/8 15:06
 */
public class IntegerOverflow {
    public static void main(String[] args) {
        //左边界
        int l = 0;
        //右边界
        int r = Integer.MAX_VALUE - 1;
        //中间索引
        int m = (l+r) / 2;
        System.out.println(m);
 
        //如果查找的中间值的右侧，要修改左边界
        l = m + 1;
        m = (l+r) / 2;
        System.out.println(m);
    }
}

第一次计算其实还没有问题，虽然R已经非常大了，但是L非常小，所以它俩加起来并不会超过整数存储范围。

但是如果我们要查找的值在中间值右侧，就要修改左边界，这个时候L+R，就会超过整数存储范围，从而造成整数溢出问题。

第一种解决方法：

int m = l + (r - l) / 2;

 

第二种解决方法：

int m = (l + r) >>> 1;

注：>>> 是移位运算。这种方法在效率上比除法高。

5、相关面试题

5.1 有一个有序表为 1,5,8,11,19,22,31,35,40,45,48,49,50 当二分查找值为 48 的结点时，查找成功需要比较的次数 。

解题口诀：奇数二分取中间，偶数二分取中间靠左

5.2 在拥有128个元素的数组中二分查找一个数，需要比较的次数最多不超过多少次

解题方案：

第一种是

 第二种是