二分算法
# 引入
题目：一个按照非递减顺序排列的整数数组 nums，找出第一个大于等于 target 的数字下标
C++提供了lower_bound库函数来解决对应问题
vector<int> nums = {1, 2, 66, 89, 100, 233};
cout << lower_bound(nums.begin(), nums.end(), 100) - nums.begin(); // 4
cout << lower_bound(nums.begin(), nums.end(), 500) - nums.begin(); // nums.size() = 6
2
3
我们使用二分查找来实现以及拓展(三种写法)：
int lower_bound1(vector<int> &nums, int target) {
// [left, right]
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
int lower_bound2(vector<int> &nums, int target) {
// [left, right)
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
int lower_bound3(vector<int> &nums, int target) {
// (left, right)
int left = -1, right = nums.size();
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
return right;
}
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
四种类型：
>=(x)>(x)转换>=(x + 1)<(x)转换>=(x) - 1<=(x)转换>(x) - 1
# 二分查找
# 34.在排序数组中查找元素的第一个和最后一个位置
题目：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
示例：输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
class Solution {
public:
int findFirst(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
vector<int> searchRange(vector<int>& nums, int target) {
// 非递减顺序排列：二分
// 返回[>= target, > target - 1]
int start = findFirst(nums, target);
if (start == nums.size() || nums[start] != target) {
return {-1, -1};
}
return {start, findFirst(nums, target + 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
# 162.寻找峰值
题目：峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞
示例：输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2
class Solution {
public:
int findPeakElement(vector<int>& nums) {
// 返回任何一个峰值（严格大于左右相邻值）所在下标
int l = 0, r = nums.size() - 1;
while(l < r) {
int mid = l + (r - l) / 2;
if(nums[mid] < nums[mid + 1]) {
l = mid + 1;
}
else {
r = mid;
}
}
return l;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 153.寻找旋转排序数组中的最小值
题目：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
示例：输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] > nums[n - 1]) {
l = mid + 1;
} else {
r = mid;
}
}
return nums[l];
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 二分答案
# 875.爱吃香蕉的珂珂
题目：珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。珂珂可以决定她吃香蕉的速度 k（单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
示例：输入：piles = [3,6,7,11], h = 8 输出：4
class Solution {
public:
bool check(vector<int>& piles, int h, int k) {
int time = 0;
for (auto& pile : piles) {
time += (pile - 1) / k + 1;
if (time > h) {
return false;
}
}
return true;
}
int minEatingSpeed(vector<int>& piles, int h) {
// 吃香蕉速度的范围：[1, INT_MAX]
int left = 1, right = INT_MAX;
while (left < right) {
int mid = left + (right - left) / 2;
if (check(piles, h, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
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
- ⌈ x / y ⌉ = (x - 1) / y + 1
- ⌊x / y ⌋ = x / y
# 2861.最大合金数
题目：假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[x] 份 x 类型金属，而每购入一份 x 类型金属需要花费 cost[x] 的金钱。给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。所有合金都需要由同一台机器制造。返回公司可以制造的最大合金数。
示例：输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3] 输出：2 解释：最优的方法是使用第 1 台机器来制造合金。要想制造 2 份合金，我们需要购买：
- 2 份第 1 类金属。
- 2 份第 2 类金属。
- 2 份第 3 类金属。
总共需要 2 _ 1 + 2 _ 2 + 2 * 3 = 12 的金钱，小于等于预算 15
class Solution {
public:
bool check(int budget, vector<vector<int>>& composition, vector<int>& stock,
vector<int>& cost, int num) {
long long ret = 0;
int k = composition.size();
int n = composition[0].size();
for (int i = 0; i < k; i++) {
long long sum = 0;
for (int j = 0; j < n; j++) {
sum += max(static_cast<long long>(composition[i][j]) * num - stock[j], 0LL) * cost[j];
}
if (sum <= budget)
return true;
}
return false;
}
int maxNumberOfAlloys(int n, int k, int budget,
vector<vector<int>>& composition, vector<int>& stock,
vector<int>& cost) {
int l = 0, r = 2e8;
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(budget, composition, stock, cost, mid)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return l - 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
