Java基础数据结构 1.2 二分查找法

1.2 二分查找

需求：

​ 在一个有序数组A中，查找target

• 如果找到了 返回索引值
• 否则返回-1

实现代码

package io.github.zemise;

/**
 * <p>
 * 二分查找
 * </p>
 *
 * @author <a href= "https://github.com/zemise">Zemise</a>
 * @since 2023/6/10
 */
public class BinarySearch {

    /**
     * <p>
     * 二分查找基础版
     * <p>
     *
     * @param a      待查找的升序数组
     * @param target 待查询的目标值
     * @return int 找到返回索引，找不到返回 -1
     * @author Zemise
     * @since 2023/06/10
     */
    public static int binarySearchBasic(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;           // 设置指针和初始值
        while (i <= j) {                // i～j 范围内还有东西

            // 这里存在问题 2
            // java里这里int类型除法会自动取整，其他语言并不一定
            // int m = (i + j) / 2;

            // 完美写法
            // 这样也能适配更多语言
            int m = (i + j) >>> 1;

            if (target < a[m]) {        // 目标在左边
                j = m - 1;
            } else if (a[m] < target) { // 目标在右边
                i = m + 1;
            } else {                    // 找到了
                return m;
            }
        }

        return -1;
    }

    /*
     *  问题1: 为什么是 i <= j
     *  意味着区间内还有未比较的元素，而不是 i < j
     *  i, j指向的元素也是会参与比较的
     *
     *  问题2: (i + j) /2 有没有问题？
     *  有问题，当数字超大时，再下一步再进行加中间m值时，会出现超过基本类型的大小
     *
     *  问题3: 比较的时候，都写成小于号有什么好处？
     *  此例子是因为，本身是升序数组，比较的时候都写为小于号，会更自然不违和，更显眼
     *
     *  问题4: 此例的 while (i <= j) 此处有死循环的可能，为什么？
     *  首先，这种写法，本身在第一次判断的时候，其实 j对应的元素就已经参与过判断了。
     *  然而，如果遇到 i = j 的时候，还会继续进入循环参与判断
     *  并且，如果二者还恰好是偶数，那么他们得出的中间值 m 和 i，j相等的，因此就会导致无限循环
     */


    /**
     * <p>
     * 二分查找改进版
     * <p>
     *
     * @param a      待查找的升序数组
     * @param target 待查询的目标值
     * @return int 找到返回索引，找不到返回 -1
     * @author Zemise
     * @since 2023/06/10
     */
    public static int binarySearchAlternative(int[] a, int target) {
        int i = 0;
        int j = a.length;               // 改进第一处 j作为了边界，而不是查找目标
        while (i < j) {                 // 改进第二处

            int m = (i + j) >>> 1;

            if (target < a[m]) {
                j = m;                  // 改进第二处
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }

        return -1;
    }
}