二分查找算法 基础版

需求 一个有序数组 array，在这个数组当中去查找 target。如果找到就返回元素在数组的索引，否则找不到就返回 -1。

算法描述：array A 数组 A0 ≤  A1 ≤  A2 ≤  ... ... ≤ A n-2 ≤ A n-1

第一步 设置 i = 0 ，j = n - 1 。

第二步 如果 i > j，结束查找，也就是没找到。

第三步 设置 m = floor((i + j) / 2)，这里的m就是中间索引，floor()向下取整的作用。

第四步 如果 target < Am，设置 j = m - 1，跳回到第二步。

第五步 如果 Am < target，设置 i = m + 1，跳回到第二步。

第六步 Am = target，结束查找，就是找到了元素所在的索引。

我们寻找 元素 47。

第一次寻找：

第二次寻找的时候，此时的 m = (4 + 6) / 2 = 5，那么A5的值是47，也就是等于我们的target值，也就找到了元素。

二分查找基础版代码 java编写。

package cc.langhai.binarysearch;

/**
 * 二分查找基础版
 *
 * @author langhai
 * @date 2023-03-01
 */
public class BinarySearch {

    /**
     * 二分查找基础版
     *
     * @param arrays 升序排序的数组
     * @param target 要查找的目标值
     * @return 找到就返回索引值 没找到就返回-1
     */
    public static int binarySearchBasic(int[] arrays, int target){
        // 设置两个指针 起始指针i 结束指针j
        int i = 0, j = arrays.length - 1;
        // 范围内有元素 我们就继续查找
        while (i <= j){
            // 找到中间索引
            int m = (i + j) / 2;
            if(target > arrays[m]){
                // 目标在右边
                i = m + 1;
            }else if(target < arrays[m]){
                // 目标在左边
                j = m - 1;
            }else {
                // target值和Am值相等，找到了，返回索引。
                return m;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arrays = {1, 2, 23, 45, 46, 47, 89};
        int i = binarySearchBasic(arrays, 47);
        System.out.println(i);
    }
}

为什么是 i <= j，而不是 i < j ？循环结束条件

i j 它们指向的元素也会参与比较。下面查找元素1在哪一个索引。

这个时候第三次查找，假如这个循环条件是 i < j而不是 i <= j，0 < 0肯定是不满足的，所以说会结束循环，从而找不到这个元素1所在的索引位置。

中间索引为什么不用 ( i + j) / 2 ???

因为 java当中二进制当中会把最高位视为符号位，假设i + j的数值大于整数的最大的数值，那么它的索引值就会变成一个负数。这显然是不合理的，所以我们要采用 (i + j) >>> 1。这个符号是 无符号右移运算符，移动一位。