二分查找

LeetCode 704 https://leetcode.cn/problems/binary-search/description/ 难度：简单 红蓝染色法，开区间二分。满足条件 nums[mid] >= target 更新 right = mid。更新什么什么就是答案，本题 right 就是答案。 时间复杂度：O(logn)，其中 n 为 nums 的长度。 空间复杂度：O(1)。 ...

LeetCode 4 https://leetcode.cn/problems/median-of-two-sorted-arrays/description/ 难度：困难 本题难度较大。 灵神题解：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/2950686/tu-jie-xun-xu-jian-jin-cong-shuang-zhi-z-p2gd/ 时间复杂度：O(logmin(m,n))，其中 m 是 a 的长度，n 是 b 的长度。注：这个复杂度比题目所要求的 O(log(m+n)) 更优。 空间复杂度：O(1)。 ...

LeetCode 300 https://leetcode.cn/problems/longest-increasing-subsequence/description/ 难度：中等 本题求最长上升子序列（LIS）有两种做法，分别是动态规划和贪心。 ...

LeetCode 33 https://leetcode.cn/problems/search-in-rotated-sorted-array/description/ 难度：中等 本题是二分查找的应用，使用红蓝染色法。如果 mid 就是 target 或者在 target 右侧，染为蓝色，如果在 target 左侧，染为红色。 如果数组被旋转了，那么分为左右两段，左边一段的元素大于最后一个元素。 对于节点 i 被染为蓝色分为以下情况： 如果 nums[i] > end，也就是 i 在左边这段。那么需要 target 也在左边这段，并且在他左边。 如果 nums[i] <= end，也就是 i 在右边这段。那么需要 target 要么在左边这段，要么在右边这段但是在他左边。 由于最后一个元素一定在 target 右边，初始就为蓝色，因此二分区间为 [0, n - 2]。 时间复杂度：O(logn)，其中 n 为 nums 的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...