427 字
2 分钟
算法 : 二分查找
设 nums 为递增（非递减）数组，长为 n。
常用转化：
| 需求 | 写法 | 如果不存在 |
|---|---|---|
≥ x 的第一个元素的下标 | lowerBound(nums, x) | 结果为 n |
> x 的第一个元素的下标 | lowerBound(nums, x + 1) | 结果为 n |
< x 的最后一个元素的下标 | lowerBound(nums, x) - 1 | 结果为 -1 |
≤ x 的最后一个元素的下标 | lowerBound(nums, x + 1) - 1 | 结果为 -1 |
| 需求 | 写法 |
|---|---|
< x 的元素个数 | lowerBound(nums, x) |
≤ x 的元素个数 | lowerBound(nums, x + 1) |
≥ x 的元素个数 | n - lowerBound(nums, x) |
> x 的元素个数 | n - lowerBound(nums, x + 1) |
注意 <x 和 ≥x 互为补集，元素个数之和为 n。≤x 和 >x 同理
class Solution {public: vector<int> searchRange(vector<int>& nums, int target) { int start = lowerBound(nums,target); if(start == nums.size() || nums[start] != target) return {-1, -1}; int end = lowerBound(nums,target + 1) - 1; return {start,end}; } int lowerBound(vector<int>& nums, int target){ //返回>=k的一个元素下标 int l = 0, r = nums.size() - 1; int m = 0; while(l <= r){ m = l + (r - l) / 2; if(nums[m] >= target){ r = m - 1; }else{ l = m + 1; } } return l; }};§1.1 基础
§1.2 进阶
部分题目需要先排序，然后在有序数组上二分查找。
class Solution { //[1385. 两个数组间的距离值 - 力扣（LeetCode）](https://leetcode.cn/problems/find-the-distance-value-between-two-arrays/description/)public: int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) { ranges::sort(arr2); int ans = 0; for(int& num : arr1){ auto it = ranges::lower_bound(arr2,num - d); if(it == arr2.end() || *it > num + d){ ans++; } } return ans; }};