二分-STL算法库
下面是二分查找相关的一些STL算法函数, 方便之后使用, 手写二分熟悉之后用STL刷题会更加快速.
计数: count和count_if
一般查找: find和find_if
基本二分查找: binary_search
寻找下边界: lower_bound
寻找上边界: upper_bound
寻找边界: equal_range
二分查找模板(基础版)
左闭右闭区间(常用)
class Solution {
public:
int search(vector<int>& nums, int target) {
int l{}, r = nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] > target)
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
};
左闭右开区间(常见)
class Solution {
public:
int search(vector<int>& nums, int target) {
int l{}, r = nums.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] > target)
r = mid;
else
l = mid + 1;
}
return -1;
}
};
左开右闭区间(几乎没见过)
class Solution {
public:
int search(vector<int>& nums, int target) {
int l{-1}, r = nums.size() - 1;
while (l + 1 <= r) {
int mid = l + 1 + (r - l - 1) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] > target)
r = mid - 1;
else
l = mid;
}
return -1;
}
};
左开右开区间(可能用到)
class Solution {
public:
int search(vector<int>& nums, int target) {
int l{-1}, r = nums.size();
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] > target)
r = mid;
else
l = mid;
}
return -1;
}
};
题目
基础
-
class Solution { public: int search(vector<int>& nums, int target) { int l{}, r = nums.size() - 1; while (l <= r) { int m = l + (r - l) / 2; if (nums[m] == target) return m; else if (nums[m] < target) l = m + 1; else r = m - 1; } return -1; } }; -
class Solution { public: int searchInsert(vector<int>& nums, int target) { int l{}, r = nums.size() - 1; while (l <= r) { int m = l + (r - l) / 2; if (nums[m] == target) return m; else if (nums[m] < target) l = m + 1; else r = m - 1; } return l; } }; -
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）;
手写二分:
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int n = nums.size(); if (!n) { return {-1, -1}; } auto f=[&](int ta) { int l{}, r{n-1}; while (l <= r) { int m=l+(r-l)/2; if (nums[m] < ta) { l=m+1; } else { r=m-1; } } return l; }; auto l = f(target);//left bound auto r = f(target+1); if (l<0 or r>n or l>=r) { return {-1,-1}; } return {l, r-1}; } };STL方法:
class Solution { public: vector<int> searchRange(vector<int> &nums, int target) { // 查找第一个大于等于的位置 auto start = lower_bound(nums.begin(), nums.end(), target); if (start == nums.end() || *start != target) return {-1, -1}; // 查找第一个大于的位置 auto end = upper_bound(nums.begin(), nums.end(), target); int st = start - nums.begin(), ed = end - nums.begin() - 1; return {st, ed}; } };
进阶
寻找旋转数组的最小值
不重复数组:
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）;
class Solution {
public:
int findMin(vector<int>& nums) {
int l{}, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > nums[r])
l = mid + 1;
else
r = mid;
}
return nums[l];
}
};
// 剑指offer
class Solution {
public:
int findMin(vector<int>& nums) {
int l{}, r = nums.size() - 1;
int m{l}; // 针对已经排好序的数组(旋转了n次的数组)
while (nums[l] >= nums[r]) {
if (r - l <= 1) {
m = r;
break;
}
m = l + (r - l) / 2;
if (nums[m] >= nums[l])
l = m;
else if (nums[m] <= nums[r])
r = m;
}
return nums[m];
}
};
重复数组(需要考虑最后一位以及相等情况):
剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode）; 154. 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）;
class Solution {
public:
int findMin(vector<int>& nums) {
int l{}, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > nums[r])
l = mid + 1;
else if (nums[mid] < nums[r])
r = mid;
else
--r; // 重复
}
return nums[l];
}
};
公平数组
力扣周赛原题.
6355. 统计公平数对的数目 - 力扣（LeetCode）;
不熟悉STL的苦逼写法:
class Solution {
public:
long long countFairPairs(vector<int>& nums, int lower, int upper) {
sort(nums.begin(), nums.end());
int n = nums.size();
long long ans{};
auto find = [&](int idx, int low) {
int r = n - 1, l = idx + 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] + nums[idx] < low)
l = mid + 1;
else
r = mid - 1;
}
return l;
};
for (int i{}; i < n; ++i) ans += find(i, upper + 1) - find(i, lower);
return ans;
}
};
熟悉了STL之后:
class Solution {
public:
long long countFairPairs(vector<int>& nums, int lower, int upper) {
sort(nums.begin(), nums.end());
long long ans{};
for (int i{}; i < nums.size(); ++i)
ans +=
upper_bound(nums.begin(), nums.begin() + i, upper - nums[i]) -
lower_bound(nums.begin(), nums.begin() + i, lower - nums[i]);
return ans;
}
};