二分查找 Java 实现 避开细节坑

• 二分查找的细节坑
• • 1、使用什么样子的区间？
  • 2、while （？？？）条件是什么
  • 3、进行数值溢出的优化
  • • 3.1、优化的两种方式：
    • • （1）使用减法代替
      • （2）使用位运算代替
• 测试代码以及二分查找代码

本文使用了左闭右闭的区间

因为在使用左闭右闭的时候，当 left = right 必须继续进行一次查找，否则漏掉了一次比较，只有当 left > right 的时候，才是全部比较好了；

mid = (left + right) / 2 时候，可能造成溢出，详情见下面代码，所以进行优化

// https://leetcode-cn.com/problems/binary-search/
public class 二分查找 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        int rs = binarySearch(arr, 2);
        System.out.println("找到的数组的下标为：" + rs);

        System.out.println(Math.pow(2, 40));
    }

    
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int mid;
        int NOT_FOUND = -1;

        
        while (left <= right) {
            // mid 的数值需要进行迭代的处理，因为是变化的
            mid = (left + right) / 2; // int 有一种向着下面取整的含义 ，每次将中间的这个结点进行更新即可
            if (target < arr[mid]) {
                right = mid - 1; // 因为比中间的小，不是中间的这个，所以查找的数据在中间的前面一位
            } else if (target > arr[mid]) {
                left = mid + 1;  // 同样的思路，比当前中间的大，不是中间的，查找的数据在中间数据的前面
            } else {
                return mid;     // 返回找到的元素的下标
            }
        }
        return NOT_FOUND;
    }

    
    public static int binarySearchPreventOverflow(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int mid;
        int NOT_FOUND = -1;

        while (left <= right) {
            mid = left + (right - left) / 2;
            // 高级玩法 使用无符号右移一位的操作
            // mid = left + (right - left) >>> 1; 就是除以二使用了位运算代替了一下而已

            if (target < arr[mid]) {
                right = mid - 1;
            } else if (target > arr[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return NOT_FOUND;
    }
}