二分查找与二叉树的中序遍历—二分查找

通关进度

题目 说明
二分查找 通关
递归和迭代的二分查找 通关
存在重复元素的二分查找 通关

参考资料

二叉树的中序遍历与二分查找问题

基本查找

1
2
3
4
5
6
7
8
public int search(int[] arr, int key) {
      for (int i = 0; i < arr.length; i++) {
          if (arr[i] == key) {
              return i;
          }
      }
      return -1;
  }

二分查找与分治

迭代方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int binarySearch(int[] array, int low, int high, int target) {

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            high = mid -1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int binarySearch(int[] array, int low, int high, int target) {

    if (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            return binarySearch(array, low, mid - 1, target);
        } else {
            return binarySearch(array, mid + 1, high, target);
        }
    }
    return -1;
}

存在重复元素的二分查找

如果存在重复元素，请找出重复元素中的左侧第一个元素

关键在于：找到目标结果后不是返回，，而是继续向左侧移动

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
public int binarySearch(int[] nums, int target) {

    if (nums.length == 0 || nums == null) {
        return -1;
    }
    int low = 0, high = nums.length -1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (nums[mid] < target) {
            low = mid + 1;
        } else if (nums[mid] > target) {
            high = mid + 1;
        } else {
            // 找到该元素后，继续向左边查找
            while (mid != 0 && nums[mid] == target) {
                mid--;
            }
            if (mid == 0 && nums[mid] == target) {
                return mid;
            }
            // while 结束后 mid ≠ target，因此需要 mid + 1
            // 比如 {1,2,2,2,2,3,3}，target = 3
            // 当 while 退出时，nums[mid] = 2，因此返回 mid + 1
            return mid + 1;
        }
    }
    return -1;
}

扩展

  • 假如重复的数量特别多，怎么办？
    此时可以对内层的 while 进一步二分，在找到目标元素后继续递归查找

【更多问题 1】寻找大于等于某数最左侧的位置

在一个有序数组中，找大于等于某个数最左侧的位置 [重要]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int nearestIndex(int[] arr, int value) {
    int left = 0;
    int right = arr.length - 1;
    int mid = 0;
    int index = -1;

    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] >= value) { // value 落在左边
            index = mid;
            right = mid - 1;
        } else { // value 落在右边
            left = mid + 1;
        }
    }
    return index;
}

【更多问题 2】 局部最小值问题

局部最小值

二分查找与二叉树的中序遍历—二分查找与搜索树高频问题

通关进度

题目 说明
山脉数组的峰顶索引 通关
寻找旋转排序数组中的最小值 通关
寻找缺失数字 通关
优化求平方根 通关
中序与搜索树原理 通关
二叉树中搜索特定值 通关
验证二叉搜索树 通关

二分查找拓展

山脉数组的峰顶索引

852. 山脉数组的峰顶索引

问题

【LeetCode 852】：符合下列属性的数组 arr 称为 山脉数组 ：

  • arr.length >= 3
  • 存在 i（0 < i < arr.length - 1）使得：
    • arr[0] < arr[1] < ... arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回满足给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i

枚举

  • 当遍历到下标 i 时，如果有 $arr{i−1}< arr_i >arr{i+1}$，，那么 i 就是需要找出的下标
  • 即只需要让 i 满足 $arri > arr{i+1}$
  • 在遍历的过程中，最先遍历到的满足 $arri > arr{i+1}$ 的下标 i 一定也满足 $arr{i-1} arr{i+1}$ 的位置
1
2
3
4
5
6
7
8
9
10
public int peakIndexInMountainArray(int[] arr) {
    int ans = -1;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > arr[i + 1]) {
            ans = i;
            break;
        }
    }
    return ans;
}

二分查找

  • 假设题目要求的下标 $i$ 为 $i_{ans}$
  • 当 $i<i{ans}$ 时，$arr_i < arr{i+1}$ （递增排列）恒成立
  • 当 $i ≥ i{ans}$ 时，$arr_i > arr{i+1}$ （递减排列） 恒成立
  • 因此 $i{ans}$ 即为「最小的满足 $arr_i > arr{i+1}$ 的下标」
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int peakIndexInMountainArray(int[] arr) {
    int left = 0, right = arr.length -1, ans = -1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (arr[mid] > arr[mid + 1]) {
            // 找到第一个  arr[mid] 使 arr[mid] > arr[mid + 1]
            ans = mid;
            // 继续向左找
            right = mid - 1;
        } else { // 向右找
            left = mid + 1;
        }
    }
    return ans;
}

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

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

问题

【LeetCode 153】：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。

数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

二分查找

一个不包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：

其中横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标。
考虑数组中的最后一个元素 $x$：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 $x$；而在最小值左侧的元素，它们的值一定都严格大于 $x$。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。

在二分查找的每一步中，左边界为 low，右边界为 high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素 nums[pivot] 与右边界元素 nums[high] 进行比较，可能会有以下的三种情况：

第一种情况是 nums[pivot]<nums[high]。如下图所示，这说明 nums[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。

第二种情况是 nums[pivot]>nums[high]。如下图所示，这说明 nums[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。

由于数组不包含重复元素，并且只要当前的区间长度不为 1，pivot 就不会与 high 重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot]=nums[high] 的情况。
当二分查找结束时，我们就得到了最小值所在的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int findMin(int[] nums) {
    int low = 0;
    int high = nums.length - 1;
    while (low < high) {
        int pivot = low + (high - low) / 2;
        if (nums[pivot] < nums[high]) {
            high = pivot;
        } else {
            low = pivot + 1;
        }
    }
    return nums[low];
}

寻找缺失数字

LCR 173. 点名

问题

【剑指 Offer】：一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0~n-1 之内。在范围 0~n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出该数字

使用二分查找，在缺失数字前，必然有 nums[i] == i，在缺失数字之后必然有 nums[i] != i，因此需要二分查找出第一个 nums[i] != i，此时的下标 i 即为所求，如果数组中没有找到下标，那么缺失的就是 n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int takeAttendance(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {

        int mid = left + ((right - left) >> 1);
        if (arr[mid] == mid) {
            // 向右查找
            left = mid + 1;
        } else { // 向左查找
            right = mid - 1;
        }
    }
    return left;
}

优化求平方根

LCR 072. x 的平方根

问题

【剑指 Offer】：使用最快方式求平方根

由于 $x$ 平方根的整数部分 ans 是满足 $k^2≤x$ 的最大 k 值，因此可以对 k 进行二分查找，从而得到答案。

二分查找的下界为 0，上界可以粗略地设定为 x，在二分查找的每一步中，只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 ans 后，也就不需要再去尝试 ans+1 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int sqrt(int num) {

    int left = 0, right = num, ans = - 1;

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

        if ((long) mid * mid <= num) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

更多问题

  • CC 150 面试题 53：在排序数组中查找数字
  • LeetCode 34：在排序数组中查找元素的第一个和最后一个位置
  • LeetCode 875：爱吃香蕉的珂珂
  • LeetCode 29：两数相除

中序与搜索树原理

二叉搜索树中搜索特定值

700. 二叉搜索树中的搜索

问题

【LeetCode 700】：给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

递归

  • 若 root 为空，则返回空节点
  • 若 val = root.val，则返回 root
  • 若 val < root.val，则递归左子树
  • 若 val > root.val，则递归右子树
1
2
3
4
5
6
7
8
9
10
public TreeNode searchBST(TreeNode root, int val) {

    if (root == null) {
        return null;
    }
    if (val == root.val) {
        return root;
    }
    return searchBST(val < root.val ? root.left : root.right, val);
}

迭代

  • 若 root 为空则跳出循环，并返回空节点；
  • 若 val=root.val，则返回 root；
  • 若 val<root.val，将 root 置为 root.left；
  • 若 val>root.val，将 root 置为 root.right。
1
2
3
4
5
6
7
8
9
public TreeNode searchBST(TreeNode root, int val) {
    while (root != null) {
        if (val == root.val) {
            return root;
        }
        root = val < root.val ? root.left : root.right;
    }
    return null;
}

验证二叉搜索树

98. 验证二叉搜索树

问题

【LeetCode 98】：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

递归

  • 函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 $(l,r)$ 的范围内（注意是开区间）
  • 如果 root 节点的值 val 不在 $(l,r)$ 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。
  • 递归调用左子树时，需要把上界 upper 改为 root.val
  • 递归调用右子树时，需要把下界 lower 改为 root.val
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

public boolean isValidBST(TreeNode node, long lower, long upper) {
    if (node == null) {
        return true;
    }
    if (node.val <= lower || node.val > upper) {
        return false;
    }
    return isValidBST(node.left, lower, node.val) &&
            isValidBST(node.right, node.val, upper);
}

中序遍历

  • 二叉搜索树「中序遍历」得到的值构成的序列一定是升序的
  • 在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可
  • 如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isValidBST(TreeNode root) {

    Stack<TreeNode> stack = new Stack<>();
    double inorder = -Double.MAX_VALUE;

    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        if (!stack.isEmpty()) {
            root = stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder) {
                return false;
            }
            inorder = root.val;
            // 转向右分支
            root = root.right;
        }
    }
    return true;
}

拓展

二分查找与二叉树的中序遍历—进阶问题

通关进度

题目 说明
有序数组转为二叉搜索树 通关
寻找两个正序数组的中位数 通关

有序数组转为搜索二叉树

108. 将有序数组转换为二叉搜索树

问题

【LeetCode 108】：给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

给定二叉搜索树的中序遍历，不能唯一地确定二叉搜索树

如果没有要求二叉搜索树的高度平衡，则任何一个数字都可以作为二叉搜索树的根节点，因此可能的二叉搜索树有多个。

如果增加一个限制条件，即要求二叉搜索树的高度平衡，不能唯一地确定二叉搜索树

可以选择中间数字作为二叉搜索树的根节点，这样分给左右子树的数字个数相同或只相差 1，可以使得树保持平衡

  • 如果数组长度是奇数，则根节点的选择是唯一的
  • 如果数组长度是偶数，则可以选择中间位置左边的数字作为根节点或者选择中间位置右边的数字作为根节点，选择不同的数字作为根节点则创建的平衡二叉搜索树也是不同的

递归的基准情形是平衡二叉搜索树不包含任何数字，此时平衡二叉搜索树为空

  • 在给定中序遍历序列数组的情况下，每一个子树中的数字在数组中一定是连续的，因此可以通过数组下标范围确定子树包含的数字，下标范围记为 [left,right]
  • 对于整个中序遍历序列，下标范围从 left=0 到 right=nums.length−1。当 left>right 时，平衡二叉搜索树为空。

中序遍历，总是选择中间位置左边的数字作为根节点

选择中间位置左边的数字作为根节点，则根节点的下标为 mid=(left+right)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public TreeNode sortedArrayToBST(int[] nums) {

    return helper(nums, 0, nums.length - 1);
}

public TreeNode helper(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }

    // 总是选择中间位置左边的数字作为根节点
    int mid = (left + right) / 2;

    TreeNode root = new TreeNode(nums[mid]);
    root.left = helper(nums, left, mid - 1);
    root.right = helper(nums, mid + 1, right);
    return root;
}

中序遍历，总是选择中间位置右边的数字作为根节点

选择中间位置右边的数字作为根节点，则根节点的下标为 mid=(left+right+1)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
public TreeNode helper(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }

    // 总是选择中间位置右边的数字作为根节点
    int mid = (left + right + 1) / 2;

    TreeNode root = new TreeNode(nums[mid]);
    root.left = helper(nums, left, mid - 1);
    root.right = helper(nums, mid + 1, right);
    return root;
}

中序遍历，选择任意一个中间位置数字作为根节点

选择任意一个中间位置数字作为根节点，则根节点的下标为 mid=(left+right)/2 和 mid=(left+right+1)/2 两者中随机选择一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Random rand = new Random();

public TreeNode sortedArrayToBST(int[] nums) {
    return helper(nums, 0, nums.length - 1);
}

public TreeNode helper(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }

    // 选择任意一个中间位置数字作为根节点
    int mid = (left + right + rand.nextInt(2)) / 2;

    TreeNode root = new TreeNode(nums[mid]);
    root.left = helper(nums, left, mid - 1);
    root.right = helper(nums, mid + 1, right);
    return root;
}

寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数

问题

【LeetCode 4】：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数

思路

  • 使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。
  • 不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 0 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int length1 = nums1.length, length2 = nums2.length;
    int totalLength = length1 + length2;
    if (totalLength % 2 == 1) {
        int midIndex = totalLength / 2;
        double median = getKthElement(nums1, nums2, midIndex + 1);
        return median;
    } else {
        int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
        double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
        return median;
    }
}

public int getKthElement(int[] nums1, int[] nums2, int k) {
    /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
        * 这里的 "/" 表示整除
        * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
        * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
        * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
        * 这样 pivot 本身最大也只能是第 k-1 小的元素
        * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
        * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
        * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
        */

    int length1 = nums1.length, length2 = nums2.length;
    int index1 = 0, index2 = 0;
    int kthElement = 0;

    while (true) {
        // 边界情况
        if (index1 == length1) {
            return nums2[index2 + k - 1];
        }
        if (index2 == length2) {
            return nums1[index1 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[index1], nums2[index2]);
        }
        
        // 正常情况
        int half = k / 2;
        int newIndex1 = Math.min(index1 + half, length1) - 1;
        int newIndex2 = Math.min(index2 + half, length2) - 1;
        int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
        if (pivot1 <= pivot2) {
            k -= (newIndex1 - index1 + 1);
            index1 = newIndex1 + 1;
        } else {
            k -= (newIndex2 - index2 + 1);
            index2 = newIndex2 + 1;
        }
    }
}