二分法算法题目集合

leetcode300 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

题解

常规做法是通过一维数组存储当前位置作为结尾的最大子序列长度。 而根据推理可知，若在从左向右遍历时，当前元素不能与已有元素构成更长的子序列，那么替换更小的元素将有更大的可能性构成更长子序列。

int lengthOfLIS(vector<int>& nums) {
    auto end = nums.begin();
    for (int x : nums) {
        auto it = lower_bound(nums.begin(), end, x);
        *it = x;
        if (it == end) {
            end ++;
        }
    }
    return end - nums.begin();
}

排序序列找区间或值

leetcode34 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

思路

1. 直接定位，向两个方向找到区间边缘
2. 定位左边界，再定位右边界

leetcode74 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵： 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

思路

• 二分定位行
• 二分定位元素