在查找算法中，二分查找法是比较高效的查找算法之一，同时二分查找的思路可以应用在很多地方，以下列举一个在Leetcode上的题
Leftmost Column with at Least a One
(This problem is an interactive problem.) A binary matrix means that all elements are
0or1. For each individual row of the matrix, this row is sorted in non-decreasing order. Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a1in it. If such index doesn’t exist, return-1. You can’t access the Binary Matrix directly. You may only access the matrix using aBinaryMatrixinterface:
BinaryMatrix.get(row, col)returns the element of the matrix at index(row, col)(0-indexed).BinaryMatrix.dimensions()returns a list of 2 elements[rows, cols], which means the matrix isrows * cols.Submissions making more than
1000calls toBinaryMatrix.getwill be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification. For custom testing purposes you’re given the binary matrixmatas input in the following four examples. You will not have access the binary matrix directly.Example 1:
Input: mat = [[0,0],[1,1]]
Output: 0
Example 2:
Input: mat = [[0,0],[0,1]]
Output: 1
Example 3:
Input: mat = [[0,0],[0,0]]
Output: -1
Example 4:
Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1
Constraints:
rows == mat.lengthcols == mat[i].length1 <= rows, cols <= 100mat[i][j]is either0or1.mat[i]is sorted in a non-decreasing way.
/*** // This is the BinaryMatrix's API interface.* // You should not implement it, or speculate about its implementation* class BinaryMatrix {* public:* int get(int x, int y);* vector<int> dimensions();* };*/class Solution {public:int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {vector<int> dim = binaryMatrix.dimensions();int n = dim[0];if(n == 0)return -1;int m = dim[0];if(m == 0)return -1;stack<int>row;for(int i = 0; i < n; i++){if(binaryMatrix.get(i, m - 1) == 1)row.push(i);}if(row.empty())return -1;int hi = m - 1;int lo = 0;while(row.size() > 1 && lo < hi){int mid = (hi + lo) / 2;stack<int>tmp;stack<int>store = row;while(!store.empty()){int cur = store.top();store.pop();if(binaryMatrix.get(cur, mid) == 1)tmp.push(cur);}if(tmp.size() == 0)lo = mid + 1;else{row = tmp;hi = mid;}}if(row.size() == 1){int cur = row.top();for(int i = lo; i <= hi; i++){if(binaryMatrix.get(cur, i) == 1)return i;}}if(lo >= hi)return lo;return -1;}};
题目提供了两种思路，二分查找是最基本的思路
Note1: (Binary Search) For each row do a binary search to find the leftmost one on that row and update the answer.
Note2: (Optimal Approach) Imagine there is a pointer p(x, y) starting from top right corner. p can only move left or down. If the value at p is 0, move down. If the value at p is 1, move left. Try to figure out the correctness and time complexity of this algorithm.
力扣35 搜索插入位置
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题很明显是二分查找，需要注意的是对于右边界的判断
class Solution {public:int searchInsert(vector<int>& nums, int target) {int size = nums.size();if(size == 0)return 0;if(nums[0] >= target)return 0;if(nums[size-1] < target)return size;int start = 0;int end = size - 1;while(start < end){int mid = start + (end - start)/2;if(nums[mid] == target)return mid;else if(nums[mid] > target)end = mid;elsestart = mid + 1;}return start;}};
下面的这种解法是用到了STL
class Solution {public:int searchInsert(vector<int>& nums, int target) {if (nums.size() == 0){nums.push_back(target);return 1;}if(find(nums.begin(), nums.end(), target) == nums.end()){register int i = 0;for (;i < nums.size(); i++){if(nums[i] > target)return i;}return i;}else{for (int i = 0; i < nums.size(); i++){if(nums[i] == target)return i;}}}};
力扣441 排列硬币
441. 排列硬币
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
示例 1:
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.
示例 2:
n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/arranging-coins
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int arrangeCoins(int n) {
long left = 0, right = n;
long k, curr;
while(left <= right)
{
k = left + (right - left) / 2;
curr = k * (k + 1) / 2;
if(curr == n)
return (int)k;
if(n < curr)
{
right = k - 1;
}
else
{
left = k + 1;
}
}
return (int)right;
}
};
这道题也可以采用数学的方法去做
class Solution:
def arrangeCoins(self, n: int) -> int:
return (int)((2 * n + 0.25)**0.5 - 0.5)
LCP 08 剧情触发时间
LCP 08. 剧情触发时间
在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。一个势力的主要属性有三种，分别是文明等级（C），资源储备（R）以及人口数量（H）。在游戏开始时（第 0 天），三种属性的值均为 0。
随着游戏进程的进行，每一天玩家的三种属性都会对应增加，我们用一个二维数组 increase 来表示每天的增加情况。这个二维数组的每个元素是一个长度为 3 的一维数组，例如 [[1,2,1],[3,4,2]] 表示第一天三种属性分别增加 1,2,1 而第二天分别增加 3,4,2。
所有剧情的触发条件也用一个二维数组 requirements 表示。这个二维数组的每个元素是一个长度为 3 的一维数组，对于某个剧情的触发条件 c[i], r[i], h[i]，如果当前 C >= c[i] 且 R >= r[i] 且 H >= h[i] ，则剧情会被触发。
根据所给信息，请计算每个剧情的触发时间，并以一个数组返回。如果某个剧情不会被触发，则该剧情对应的触发时间为 -1 。
示例 1：
输入： increase = [[2,8,4],[2,5,0],[10,9,8]] requirements = [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]
输出: [2,-1,3,-1]
解释：
初始时，C = 0，R = 0，H = 0
第 1 天，C = 2，R = 8，H = 4
第 2 天，C = 4，R = 13，H = 4，此时触发剧情 0
第 3 天，C = 14，R = 22，H = 12，此时触发剧情 2
剧情 1 和 3 无法触发。
示例 2：
输入： increase = [[0,4,5],[4,8,8],[8,6,1],[10,10,0]] requirements = [[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]
输出: [-1,4,3,3,3]
示例 3：
输入： increase = [[1,1,1]] requirements = [[0,0,0]]
输出: [0]
限制：
1 <= increase.length <= 10000
1 <= requirements.length <= 100000
0 <= increase[i] <= 10
0 <= requirements[i] <= 100000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ju-qing-hong-fa-shi-jian
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我的原始解法，超出时间限制
class Solution {
public:
vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
vector<int>ret(requirements.size(), -1);
vector<int>daypro{0,0,0};
for(int j = 0; j < requirements.size(); j++)
{
if(requirements[j][0] <= daypro[0] && requirements[j][1] <= daypro[1] && requirements[j][2] <= daypro[2])
ret[j] = 0;
}
for(int day = 1; day <= increase.size(); day++)
{
daypro[0] += increase[day - 1][0];
daypro[1] += increase[day - 1][1];
daypro[2] += increase[day - 1][2];
for(int j = 0; j < requirements.size(); j++)
{
if(ret[j] == -1)
{
if(requirements[j][0] <= daypro[0] && requirements[j][1] <= daypro[1] && requirements[j][2] <= daypro[2])
ret[j] = day;
}
}
}
return ret;
}
};
以下是二分查找的方法
class Solution {
public:
vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) {
vector<vector<int>> s(increase.size()+1,vector<int>(3,0));
for(int i=0;i<increase.size();i++){
for(int j=0;j<3;j++){
s[i+1][j] = s[i][j] + increase[i][j];
}
}
vector<int> ans;
for(auto v:requirements){
int l=0, r = increase.size();
while(l<r){
int m = (l+r)/2;
if(s[m][0]>=v[0]&&s[m][1]>=v[1]&&s[m][2]>=v[2])
r = m;
else
l = m+1;
}
if(s[l][0]>=v[0]&&s[l][1]>=v[1]&&s[l][2]>=v[2])
ans.push_back(l);
else
ans.push_back(-1);
}
return ans;
}
};
官方题解
题解
简化问题
在原问题比较复杂时，我们可以先考虑简化问题的情况。原问题中有三种不同的属性，三种属性均满足要求才会触发相应剧情。这里我们可以先考虑简化为只有一种属性。
解法 1
如果只有一种属性，显然我们只需要计算每一天的属性情况，最后对于所有的requirements 都在属性列表中进行二分查找（现在只有一种属性了)，就能知道他是在哪一天完成的了。
解法 2
还可以换一个思路，计算完每一天的属性情况后，我们将 requirements 中的单属性也同样进行排序，放入一个队列中。
接着，我们遍历每一天的属性情况，由于 requirements 也是排序过的，我们只需要看队首有多少元素满足当前触发要求，满足则触发就可以了。
原始问题
以上只是单属性的做法，原始题目中给了多达三种属性。但是实际上，每一种属性的满足是互相独立的。
简单来说，对于一个剧情要求 (C, R, H) 来说，假设 C 要求是在第 x 天满足的，R要求是在第 y 天满足的，H 要求是在第 z 天满足的。那么该剧情的满足时间为：t=max(x,y,z)
而每一个属性在什么时间满足，正好是我们前面提到的简化问题。至此，原始问题的解法也清晰了：
根据简化问题，分别只考虑三种属性，计算各剧情三种属性的触发时间。
根据上式计算各剧情的最终触发时间。
class Solution(object):
def getTriggerTime(self, day_increase, story_requires):
"""
:type day_increase: List[List[int]]
:type story_requires: List[List[int]]
:rtype: List[int]
"""
a = [0 for i in range(3)]
#将剧情的下标记录在story中，方便映射结果
story_requires = [x + [i] for i, x in enumerate(story_requires)]
#将requirements按三种维度分别排序，得到 s
s = [sorted(story_requires, key=lambda x: x[i]) for i in range(3)]
index = [0 for i in range(3)]
n = len(story_requires)
trigger = [0 for i in range(n)]
ans = [-1 for i in range(n)]
#枚举每一天
for d, (na,nb,nc) in enumerate(day_increase):
#计算当天的属性
a[0] += na; a[1] += nb; a[2] += nc
#遍历三种属性的排序序列，计算当前可以被触发的剧情
for i in range(3):
while index[i] < n and a[i] >= s[i][index[i]][i]:
trigger[s[i][index[i]][-1]] += 1
#如果某个剧情触发次数等于3次(三种属性均触发，剧情被实际触发)
if trigger[s[i][index[i]][-1]] == 3:
ans[s[i][index[i]][-1]] = d + 1
index[i] += 1
#第0天单独考虑
for i, (na, nb, nc, _) in enumerate(story_requires):
if na == 0 and nb == 0 and nc == 0:
ans[_] = 0
return ans
STL binary_search
binary_search有两个版本，第一个版本采用operator < 进行比较，第二个版本采用仿函数comp(i, value)进行比较。
第一个版本的比较条件是：存在一个迭代器i，当且仅当“i < value” “i > value”均不成立时，返回true
第二个版本的比较条件是：存在一个迭代器i，当且仅当“comp(i, value)”和”comp(value, *i)”皆不为真，则第二个版本返回true。
第一个版本
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator second, const T& value) {
ForwardIterator i = lower_bound(first, last, value);
return i != last && !(value < *i);
}
若有收获，就点个赞吧
0 人点赞
