matinal：如何优雅的实现二分法查找

matinal

发布于 2024-04-18 08:54:46

840

发布于 2024-04-18 08:54:46

文章被收录于专栏：SAP TechnicalSAP Technical

在介绍实现之前需要先来说一下二分法查找的定义，以及一些前置条件。

前提

数组必须是有序的

算法描述

有一个有序数组 A
定义算法的左右边界，分别为 L 和 R，循环执行二分查找。
获取中间索引 M = (L + R) / 2
中间索引的值与待查找的值 T 进行比较
中间索引的值 A[M] 与带查找的值 T 进行比较 4.1 A[M] = T 表示找到，返回中间索引 4.2 A[M] > T 中间值右侧的其它元素都大于 T，无需比较，去中间索引左边去找，M-1 设置为右边界，重新查找 4.3 A[M] < T 中间值左侧的其它元素都小于 T，无需比较，去中间索引右边去找，M-1 设置为左边界，重新查找
当 L > R 时，表示没有找到，应结束循环

算法实现

根据上面的描述，我们可以轻松的实现一版实现，如下所示：

    private static int binarySearch(int[] arr, int target){
        int left = 0, right = arr.length - 1, mid;
        while (left <= right) {
            mid = (left+ right) / 2;
            if(arr[mid] == target) {
                return mid;
            } else if(arr[mid] > target) {
                right = mid - 1;
            } else if(arr[mid] < target) {
                left = mid + 1;
            }
        }
        return -1;
    }

上面这一版实现看起来是那么的清爽，干净，但是可能会有一些 bug

注意事项

mid = (left + right) / 2; 这一行代码可能就会出现溢出问题，举个例子就明白了，假设数组的长度是 int 的最大值，target 在数组中间靠右的位置，那么第一次计算 mid 是不会有问题，再次进入 while 循环的时候，此时 left = mid + 1, 然后再计算 left + right 就会出现溢出问题了。

怎么解决这种问题呢？大家可能经常看着这种写法 left + (right - left) / 2 , 这确实可以解决问题，公式的推导过程我这里也写出来(我最开始看到这种写法惊呆了)。

(left + right) / 2 ⇒ 
left / 2 + right / 2 ⇒ 
left + (-left / 2 + right / 2) ⇒ 
left + (right - left) / 2

如果只有这种解决我还写什么呢？我主要是想介绍如下一种解决方法，使用无符号右移 1 位来表示除以 2。(left + right) >>> 1 这么写也能达到除以 2 的要求，而且更简洁，效率更高。

好了，最后在给大家贴一下完整的优雅的二分法的实现，欢迎大家拍砖讨论哈。

    private static int binarySearch(int[] arr, int target){
        int left = 0, right = arr.length - 1, mid;
        while (left <= right) {
            mid = (left+ right) >>> 1;
            if(arr[mid] == target) {
                return mid;
            } else if(arr[mid] > target) {
                right = mid - 1;
            } else if(arr[mid] < target) {
                left = mid + 1;
            }
        }
        return -1;
    }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-16，如有侵权请联系 cloudcommunity@tencent.com 删除

int