文章摘要： 摘要内容。

简介

简要说明

主要功能

注意事项

适用场景

时间复杂度

  • 最坏情况：O(log n)
  • 最好情况：若带查找元素恰好在数组中央位置，只需要循环一次 O(1)

空间复杂度

  • 需要常数个指针i、j、m，因此额外占用的空间是O(1)

Java 8

提示：将(i + j) / 2改为(i + j) >>> 1。

  • 当j的取值范围非常大，比如j达到了整数数据类型规定的最大值，当进行第一次区中间值后，在取第二个中间值时，i将等于中间值，这时会进行i + j的操作，数值将超出整数数据类型规定的最大值，最终得到的结果会变成负数，问题就此出现。
  • java将一个数的二进制表示时，会把最高位的一个二进制数作为符号位。当二进制的最高位为1的时候就代表是负数。
  • 该符号>>>代表无符号右移运算符，将在二进制数下将所有0和1向右移，高位补零。
public class Main {
    public static void main(String[] args) {
        // 待查找的数组
        int[] array = {1, 3, 5, 7, 8, 10, 12};
        // 调用算法函数
        int index = binarySearch(array, 5);
        // 显示结果
        System.out.println(index);
    }

    /**
     * 算法
     * Params:
     *     - array：待查找的数组
     *     - target：待查找的目标值
     * Returns:
     *     - 若找到则返回索引
     *     - 若没找到则返回-1
     */
    public static int binarySearch(int[] array, int target) {
        int i = 0;                  // 数组左边边界的下标
        int j = array.length - 1;   // 数组右边边界的下标

        // i~j 将要查找的范围内还有数值
        while (i <= j) {
            // `(i + j) >>> 1`代表转换为二进制下进行无符号右移1位
            // 二进制右移1位相当于除以2并取整的功能
            int m = (i + j) >>> 1;           // 创建一个中间值

            if (target < array[m]) {           // 目标在中间值的左边
                j = m - 1;
            } else if (array[m] < target) {    // 目标在中间值的右边
                i = m + 1;
            } else {                       // 目标正好就是中间值
                // 在数组成功中找到需要查找的值，返回值在该数组中的下标
                return m;
            }
        }
        // 在数组中并没有找到需要查找的值，值不在该数组中
        return -1;
    }

}
更新时间: