空间复杂度

• 介绍
• 二分查找法的空间复杂度

介绍

空间复杂度用来衡量一个算法,随着输入规模的变大,这个算法需要消耗额外的内存的大小.额外内存的意思是, 除了原始参数之外,算法运算过程需要消耗的内存.

二分查找法的空间复杂度

public static int binarySearchBasic(int[] a, int target) {
        //1. 设置左指针和右指针的初值
        int l = 0, r = a.length - 1;
        while (l <= r) // 当左右指针中间范围有元素时执行
        {
            //获取中间值的索引, 使用逻辑右移(>>>), 而不是算术右移(>>)
            int m = (l + r) >>> 1;
            //比较
            if (target < a[m]) {
                r = m - 1; // 目标值在中间值左边
            } else if (a[m] < target) {
                l = m + 1; // 目标值在中间值右边
            } else {
                return m; //中间值等于目标值, 返回中间值索引
            }
        }
        return -1; //循环内没有找到目标值

    }

在这个算法中,一共定义了三个变量: l,r,m(m并不会随着循环一次,再次多占4个字节) 这三个变量一共占用了 4 * 3 = 12 个字节. 并且随着输入的数据规模变大也不会改变. 因此这个算法的空间复杂度是$O(1)$