算法通关村第9关——二分查找与搜索树高频问题（白银）

前言：

常见的时间复杂度和对应的算法题型如下：

1. O(1) - 常数时间复杂度：不论输入规模的大小，算法都能在常数时间内完成操作。例如，访问数组中的一个元素或插入/删除链表的头节点。
   • 常数时间复杂度通常与简单的操作或直接访问数据结构中的元素相关。这种类型的算法题较少，常见的包括基本的数组或链表操作，如访问数组元素、插入/删除链表的头节点等。
2. O(log(n)) - 对数时间复杂度：算法的执行时间随着输入规模的增长而增长，但以对数的速度增长。例如，二分查找算法。
   • 对数时间复杂度通常与分治思想相关，通过每次减小问题规模的一半来进行快速搜索或排序。常见的算法题包括二分查找、二叉搜索树等。
3. O(n) - 线性时间复杂度：算法的执行时间与输入规模成正比。例如，遍历一个数组或链表中的所有元素。
   • 线性时间复杂度的算法通常需要遍历输入规模的所有元素一次。这类算法题常见于线性结构上的遍历和搜索问题，如数组、链表、栈和队列等。
4. O(n log(n)) - 线性对数时间复杂度：算法的执行时间介于线性和平方级时间复杂度之间。例如，快速排序和归并排序等基于比较的排序算法。
   • 线性对数时间复杂度的算法通常与排序和搜索相关。常见的算法题包括快速排序、归并排序、堆排序、优先队列等。
5. O(n^2) - 平方时间复杂度：算法的执行时间与输入规模的平方成正比。例如，嵌套循环遍历一个二维数组。
   • 平方时间复杂度的算法通常涉及到嵌套循环，需要遍历两次输入规模的所有元素。常见的算法题包括选择排序、插入排序、冒泡排序等。
6. O(n^k) - 多项式时间复杂度：算法的执行时间与输入规模的某个常数的幂次相关。其中 k 是一个常数。例如，三重循环遍历一个三维数组。
   • 多项式时间复杂度通常与递归或动态规划相关，存在多重循环嵌套的情况。常见的算法题包括矩阵乘法、旅行商问题等。
7. O(2^n) - 指数时间复杂度：算法的执行时间与输入规模的指数相关。例如，穷举法求解一个集合的所有子集。
   • 指数时间复杂度的算法通常与穷举法相关，需要对所有可能的解空间进行搜索。常见的算法题包括子集生成、组合问题、背包问题等。

1. 基于二分查找算法的括展问题

1.1 山脉数组的峰顶索引

leetcode 852. 山脉数组的峰顶索引

根据题意，时间复杂度为 O(log(n)) ，则可以简单得出：时间复杂度为 O(log(n)) 的解决方案一般是二分查找算法。

这道题就是二分查找基本题的变形，区别就是if判断语句不一样，不多说

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while(left < right){
            int mid = left + ((right - left) >> 1);
            if(mid <= 0 || mid >= arr.length - 1){
                return -1;
            }
            if(arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]){
                return mid;
            }
            if(arr[mid] > arr[mid - 1]){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

不过可以再简单一点：至于哪个更快，要看数据

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int mid = left + ((right - left) >> 1);

            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.2 寻找旋转排序数组中的最小值

leetcode 153. 寻找旋转排序数组中的最小值

这道题其实也算是上面那道题的变式，需要思考的就是边界值：

题意：

1. 升序排列
2. 互不相同

可以得出：mid>right的时候，最大值一定在mid的右边

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        if(nums.length == 1) return nums[0];
        if(nums[left] < nums[right]){
            return nums[left];
        } else if(nums[right] < nums[right-1]){
            return nums[right];
        }
        
        while(left < right){
            int mid = left + ((right - left) >> 1);
            if(mid == 0 || mid == nums.length - 1){
            }
            if(nums[mid] < nums[mid+1] && nums[mid] < nums[mid-1]){
                return nums[mid];
            }
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

不过我写的不够好，可以再优化一下：

下面这样看起来更清楚，而且效率会更高一点

public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + ((right - left) >> 1);

            // 检查是否已经有序，如果是则直接返回最左元素
            if (nums[left] < nums[right]) {
                return nums[left];
            } else if(nums[right] < nums[right-1]){
            	return nums[right];
            }

            // 判断mid处的元素与右边界的关系，确定搜索方向
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // 循环结束时，left和right相等，即找到了最小值
        return nums[left];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

1.3 0～n-1中缺失的数字

leetcode 剑指 Offer 53 - II. 0～n-1中缺失的数字

这道题其实就是最简单二分查找的略微变形：

1. 对于有序的也可以用二分查找，这里的关键点是在缺失的数字之前，必然有nums[i]==i，在缺失的数字之后，必然有nums[i]!=i。
2. 因此，只需要二分找出第一个nums[i]!=i，此时下标i就是答案。若数组元素中没有找到此下标，那么缺失的就是n。

代码如下：

class Solution {
    public int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        while(left <= right){
            int mid = left+((right-left) >> 1);
            if(nums[mid]>mid){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.4 x 的平方根

leetcode 69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

没什么好讲的，翻译过来就是[1,n]的数组进行二分查找

当我们在搜索平方根时，如果mid的平方等于x，即mid * mid == x，那么我们可以确定mid就是x的平方根。

这是因为我们在范围[1, x]内进行二分查找，每次取中间值mid并计算mid * mid与x的大小关系。当mid * mid等于x时，说明我们找到了x的平方根。

class Solution {
    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        int left = 1;
        int right = x;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);

            if (x / mid == mid) {
                return mid;
            } else if (x / mid > mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2. 中序与搜索树原理

二叉搜索树是一个很简单的概念，但是想说清楚却不太容易。简单来说就是如果一棵二叉树是搜索树，则按照中序遍历其序列正好是一个递增序列。比较规范的定义是：

1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值;

2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值;

3. 它的左、右子树也分别为二叉排序树。下面这两棵树一个中序序列是{3,6,9,10,14,16,19}，一个是{3,6,9,10}，因此都是搜索树：

搜索树的题目虽然也是用递归，但是与前后序有很大区别，主要是因为搜索树是有序的，就可以根据条件决定某些递归就不必执行了，这也称为“剪枝”。

2.1 二叉搜索树搜索特定值

leetcode 700. 二叉搜索树中的搜索

要注意是二叉搜索树，那么就是它的特点来写：

1. 如果根节点为空 root == null 或者根节点的值等于搜索值 val == root.val，返回根节点。

2. 如果 val < root.val，进入根节点的左子树查找 searchBST(root.left, val)。

3. 如果 val > root.val，进入根节点的右子树查找 searchBST(root.right, val)。

public TreeNode searchBST(TreeNode root, int val) {
	if (root == null || val == root.val) return root;
	return val < root.val ? searchBST(root.left, val) : searchBST(root.right
}
1
2
3
4

如果采用迭代方式，也不复杂：

1. 如果根节点不空 root != null 且根节点不是目的节点 val != root.val：

   2. 如果 val < root.val，进入根节点的左子树查找 root = root.left。

   3. 如果 val > root.val，进入根节点的右子树查找 root = root.right。

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root != null && root.val != val  ){
            if(root.val > val){
                root = root.left;
            }else{
                root = root.right;
            }
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2.2 验证二叉搜索树

有效 二叉搜索树定义如下：

1. 节点的左子树只包含 小于 当前节点的数。

2. 节点的右子树只包含 大于 当前节点的数。

3. 所有左子树和右子树自身必须也是二叉搜索树。

根据题目给出的性质，我们可以进一步知道二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。

class Solution {
    long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        // 验证左子树
        if (!isValidBST(root.left)) {
            return false;
        }

        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST
        if (root.val <= prev) {
            return false;
        }
        prev = root.val;  // 更新prev为当前节点的值

        // 验证右子树
        return isValidBST(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

递归的方式最难实现的就是在哪里写条件，有点难理解，用迭代就比较容易理解，就是比较长

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        long prev = Long.MIN_VALUE;

        while (!stack.isEmpty() || current != null) {
            // 将当前节点及其所有左子节点入栈
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            // 弹出栈顶节点，并判断是否大于前一个节点
            current = stack.pop();
            if (current.val <= prev) {
                return false;
            }
            prev = current.val;

            // 处理右子节点
            current = current.right;
        }

        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31