【面试算法笔记】0101-数组-二分查找

面试算法笔记 2026年4月·算法 LeetCode

zbhgis 浩瀚地学1976 字10 分钟

创建于 2026/4/11更新于 2026/4/11

个人主页：https://github.com/zbhgis

前言

本系列主要记录自己学习算法的过程中的感悟。

第一篇分析时空复杂度，会比较详细一点，后续都简略化。

力扣704.二分查找

链接：https://leetcode.cn/problems/binary-search/

注意点

闭区间做法。

这道题的题目关键在于如何判断边界条件。

1.left和right的初始值。在闭区间下，主要是考虑到两边都能取到值，因此left和right就是原始数组的下标边界。

2.在循环的时候left是否要等于right。如果是闭区间，那么就是left小于等于right，因为等left=right的时候，区间[left, right]是成立的，说明循环可以继续执行。

3.循环内部的左右边界条件判断。当nums[mid] > target的时候，此时target是在nums[mid]的左边，说明右边界需要收缩，此时right = mid - 1; 为啥需要减去1，是因为此时是闭区间，如果不减去1的话，那么更新后的区间[left, mid]，可是nums[mid]已经在nums[mid] > target的时候已经判断过了，说明nums[mid]一定不是我们需要的值，所有需要将mid-1，此时才能得到正确的区间[left, mid - 1]。

同理，当nums[mid] < target的时候，此时target是在nums[mid]的右边，说明左边界需要收缩，此时left = mid+ 1；为啥需要加1的道理同上一段，只有减去1才能得到下一轮循环的正确区间[mid + 1, right]。

4.要注意溢出。如果mid的确定是直接通过(left + right) / 2; 那么可能会溢出，因为当left或right中存在一个特别大的数字的时候，此时会超过int类型的取值范围。

5.最终捋一下思路，本质上通过对比nums[mid]与target的值，不断的缩短边界，从而找到所需要的值。主要是边界的判定，死记硬背记不住，而且后续还有很多变种题目。所以得搞懂各个题目的边界到底是怎么设计。

代码

Java

class Solution {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) return -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else if (nums[mid] > target) right = mid - 1;
            else return mid;
        }
        return -1;
    }
}

时空复杂度分析

1.时间

最坏情况下，每次都进行区间二分

设数组长度为 n

每次循环后剩余元素数：

第1次循环后：≤ n/2

第2次循环后：≤ n/4

第3次循环后：≤ n/8

第k次循环后：≤ n/2ᵏ

当 n/2ᵏ < 1 时结束：

n/2ᵏ < 1

n < 2ᵏ

k > log₂n

所以循环次数 ≤ log₂n

所以时间复杂度为O(logn)

2.空间

都是一些常量级别的额外空间

所以空间复杂度O(1)

力扣35.搜索插入位置

链接：https://leetcode.cn/problems/search-insert-position

注意点

这道题的题目比较简单，主要是返回值的确定。

1.当nums[mid] == target的时候，直接返回mid就行，

2.当nums[mid] < target与nums[mid] > target的时候，按照二分查找的思路一直找

3.当在数组中找不到target的时候，此时分为三种情况，在数组前面，在数组后面，在数组中间但是没有对应值。

这个时候的返回值就是left。因为当一直找不到数组中对应的target时，经过不断地二分，跳出循环的时候，left在right右边，此时right+1 = left，即跳出循环后的区间为[right, left]

当target在数组前面时，

此时right为-1，left为0，所以target插入位置为left；

当target在数组中间时，

此时target一定是落在一个区间内的，target一定比right大，比left小，所以target插入为left

当target在数组后面时，

此时left为nums.length；所以target插入位置为left；

综上，上述三种情况的返回值都是left。

4.梳理一下，整体还是按照二分查找去写，只不过现在返回值有点不一样。尤其是上述的后三种情况，经过分析，是可以统一为一种返回值的（也就是数组中找不到target的时候返回值是一样的）。

代码

Java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) right = mid - 1;
            else if (nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return left;
    }
}

时空复杂度分析

同上

力扣34. 在排序数组中查找元素的第一个和最后一个位置

链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

注意点

1.这道题的前半段就是用二分查找，找到那个target是否在nums中，不在即可直接返回[-1, -1]；

2.但如果找到了target在nums中的位置，接下来就得确定出left和right的具体位置。让left和right反向拓展。

3.边界条件中，因为涉及到left--和right++，所以left - 1和right + 1的结果均不能超出数组的下标，就是代码中的left -1 > -1 与 right + 1 < nums.length（或者写成left - 1 >= 0 与 right + 1 <= nums.length -1 可能会更加清楚一点），直到往外拓展的值都不等于target的时候，就跳出循环。

4.总结就是先用经典二分找到对应的target的可能下标，然后对下标进行区间的扩展，得到最终的结果。

代码

Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int idx = search(nums, target);
        int left = idx, right = idx;
        if (idx != -1) {
            while (left - 1 > -1 && nums[left - 1] == nums[idx]) left --;
            while (right + 1 < nums.length && nums[right + 1] == nums[idx]) right ++;
        }
        return new int[]{left, right};
    }

    private static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) right = mid - 1;
            else if (nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
}

时空复杂度分析

二分查找部分的时空复杂度分析同上，

但是这个解法加了一个线性扫描，所以最坏情况下可能会达到O(log n + n)，即O(n）

力扣34.在排序数组中查找元素的第一个和最后一个位置-解法2

链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

注意点

这道题的题目解法一比较好理解一点，解法二效率相对高一点。

1.先想办法找到left，就是target匹配的元素的开始位置，构建一个方法getLeftBound()，通过getLeftBound()得到target + 1的左边界，然后再减1就是target的右边界。

2.写getLeftBound的时候，使用闭区间的写法时，需要注意的是nums[mid] > target 和 nums[mid] == target 这两个判断合并在一起了，是进一步找到新的right。因为当nums[mid] == target的时候，如果直接返回mid，此时的mid可能是连续多个元素的中间某一个，不是最终想要的left。所以把这个情况合并给right，此时nums[mid] >= target，最终right不再进行判断时，right < mid， left不再进行判断时，left = mid，且left = right + 1。

代码

                      

-header">Java

时空复杂度分析

两次二分查找，所以为O(log n + log n) = O(log n)

空间复杂度还是O(1)

Acwing789. 数的范围

链接：https://www.acwing.com/problem/content/791/

注意点

同上

代码

Java

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i ++) {
            nums[i] = sc.nextInt();
        }
        
        while (q -- > 0) {
            int target = sc.nextInt();
            int idx = search(nums, target);
            int left = idx, right = idx;
            if (idx != -1) {
                while (left - 1 > - 1 && nums[left - 1] == nums[idx]) left --;
                while (right + 1 < nums.length && nums[right + 1] == nums[idx]) right ++;
            }
            System.out.println(left + " " + right);
        }
    }
    
    private static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) right = mid - 1;
            else if (nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
}

时空复杂度分析

同上

力扣69.x的平方根

链接：https://leetcode.cn/problems/sqrtx/description/

注意点

这道题就是跟经典二分比，需要考虑边界条件的变化。

1.由于是进行开方运算，所以right的最大值可以设定不超过Integer的平方根，此时就不要减去1

2.其他步骤类似，就是比较条件变成了mid的平方与x进行比较了

3.这里return right是因为当循环结束后，left>right，需要返回小的那个数。

代码

Java

class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = Math.min(x, (int) Math.sqrt(Integer.MAX_VALUE));

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid * mid == x) {
                return mid;
            } else if (mid * mid < x) {
                left = mid + 1;
            } else if (mid * mid > x) {
                right = mid - 1;
            }
        }
        return right;
    }
}

时空复杂度分析

类似于力扣704. 二分查找

力扣367. 有效的完全平方数

链接：https://leetcode.cn/problems/valid-perfect-square/description/

注意点

思路同力扣69. x的平方根

代码

Java

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0;
        int right = Math.min(num, (int) Math.sqrt(Integer.MAX_VALUE));
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid * mid < num) left = mid + 1;
            else if (mid * mid > num) right = mid - 1;
            else return true;
        }
        return false;
    }
}

时空复杂度分析

类似于力扣704. 二分查找

Acwing790. 数的三次方根

链接：https://www.acwing.com/problem/content/792/

注意点

1.这个是浮点数的二分查找，所以在边界条件上有很多不一样的，

2.刚开始定义的时候，直接按照给定的最大范围来定义左右指针，减少后续的判断步骤；

3.题目要求小数点后6位，因此精度可以控制在小数点后8位就能满足需求。

4.left和right在while循环中直接等于mid，因为是浮点数，所以可以不用在加1或减1，求出来的值已经是所需要的最接近的数了。

代码

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double x = sc.nextDouble();
        double left = -10000, right = 10000;
        while (right - left > 1e-8) {
            double mid = left + (right - left) / 2;
            if (mid * mid * mid < x) left = mid;
            else right = mid;
        }
        System.out.printf("%.6f", right);
    }
}

时空复杂度分析

同上

参考

https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html