二分法应用实例
最新推荐文章于 2024-03-26 10:23:07 发布
zc_zhao
最新推荐文章于 2024-03-26 10:23:07 发布
阅读量1.7k
收藏
1
点赞数
最新推荐文章于 2024-03-26 10:23:07 发布
阅读量1.7k
收藏
1
点赞数
二分法的时间复杂度
O
(
log
(
n
)
)
O(\log(n))
O(log(n)),直接遍历时间复杂度是
O
(
n
)
O(n)
O(n)。倘若数组的长度是
2
32
2^{32}
232，也就是 4294967296，那么在
O
(
n
)
O(n)
O(n)的最坏的情况下，你要查找4294967296这么多次，如果是用二分的话，最坏查找32次就可以了。
解题模板：
模板只是起到辅助作用，至于真正用的话，还是需要思考如何灵活使用它。
对于有序的数组，可以考虑使用二分，直接暴力遍历，感觉过不了呢。
int start = 0, end = nums.size() - 1;
while(start + 1 < end)
{
int mid = start + (end - start) / 2;
if( ... )
{
start = mid;
}
else
{
end = mid;
}
//灵活变动，但需要单独判断，可能并行判断，可能有优先级去判断
if（...start....）
if（...end....）
}
0.第一个错误版本(leetcode 278)
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int start = 1, end = n;
while(start+1 < end)
{
int mid = start + (end - start) / 2;
if(!isBadVersion(mid))
{
start = mid;
}
else
{
end = mid;
}
}
if(isBadVersion(start))
{
return start;
}
return end;
}
};
1.在排序数组中查找元素的第一个和最后一个位置（leetcode 34）
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
//for(int i = 0; i < 6; i++)printf("%d ",nums[i]);printf("\n");
vector<int> ret(2,-1);
int size = nums.size();
if(size == 0)
return ret;
// find front
int start = 0, end = size - 1;
while(start+1 < end)
{
int mid = start + (end - start) / 2;
//printf("start is %d, end is %d, mid is %d \n",start,end,mid);
if(nums[mid] >= target)
{
end = mid;
}
else
{
start = mid;
}
}
if(nums[start] == target)
{
ret[0] = start;
}
else if(nums[end] == target)
{
ret[0] = end;
}
//find back
start = 0, end = size - 1;
while(start+1 < end)
{
int mid = start + (end - start) / 2;
//printf("start is %d, end is %d, mid is %d \n",start,end,mid);
if(nums[mid] <= target)
{
start = mid;
}
else
{
end = mid;
}
}
if(nums[end] == target)
{
ret[1] = end;
}
else if(nums[start] == target)
{
ret[1] = start;
}
return ret;
}
};
2.搜索二维矩阵（leetcod 74）
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty() || matrix[0].empty())
return false;
int row = matrix.size();
int startRow = 0, endRow = row - 1;
while(startRow + 1 < endRow)
{
int mid = startRow + (endRow - startRow)/2;
if(matrix[mid][0] == target)
{
return true;
}
else if(matrix[mid][0] < target)
{
startRow = mid;
}
else
{
endRow = mid;
}
}
int selectRow = 0;
if(matrix[endRow][0] <= target)
{
selectRow = endRow;
}
else
{
selectRow = startRow;
}
int startCol = 0, endCol = matrix[0].size() - 1;
while(startCol+1 < endCol)
{
int mid = startCol + (endCol - startCol)/2;
if(matrix[selectRow][mid] == target)
{
return true;
}
else if(matrix[selectRow][mid] < target)
{
startCol = mid;
}
else
{
endCol = mid;
}
}
if(matrix[selectRow][startCol] == target || matrix[selectRow][endCol] == target)
return true;
return false;
}
};
3.搜索二维矩阵 III（leetcod 240）
class Solution {
public:
bool searchMatrix(vector<vector<int> >& matrix, int target) {
if(matrix.empty() || matrix[0].empty())
return false;
int numOfFind = matrix.size() < matrix[0].size() ? matrix.size():matrix[0].size();
//printf("numOfFind is %d\n",numOfFind);
for(int i = 0; i < numOfFind; i++)
{
//printf("i is %d\n",i);
bool upDown = find(matrix, i, target, true);
bool leftRight = find(matrix, i, target, false);
//printf("upDown is %d, leftRight is %d\n",upDown,leftRight);
if(upDown || leftRight)
return true;
}
return false;
}
private:
bool find(vector<vector<int> >& matrix, int i, int target, bool isFindRow)
{
int start = i, end = isFindRow?matrix.size()-1:matrix[0].size()-1;
//printf("isFindRow is %d\n",isFindRow);
while(start + 1 < end)
{
int mid = start + (end - start)/2;
//printf("start is %d, end is %d, mid is %d\n", start, end, mid);
if(isFindRow)
{
if(matrix[mid][i] < target)
{
start = mid;
}
else if(matrix[mid][i] > target)
{
end = mid;
}
else
{
return true;
}
}
else
{
if(matrix[i][mid] < target)
{
start = mid;
}
else if(matrix[i][mid] > target)
{
end = mid;
}
else
{
return true;
}
}
}
//printf("last start is %d, end is %d\n", start, end);
if(isFindRow)
{
if(matrix[start][i] == target || matrix[end][i] == target)
{
return true;
}
}
else
{
if(matrix[i][start] == target || matrix[i][end] == target)
return true;
}
return false;
}
};
4.旋转数组的最小数字（leetcod 153）
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.empty())
return 0;
int start = 0, end = nums.size() - 1;
while(start+1 < end)
{
int mid = start + (end - start)/2;
//printf("start is %d, end is %d, mid is %d\n",start,end,mid);
if(nums[mid] <= nums[end])
{
end = mid;
}
else
{
start = mid;
}
}
//printf("last start is %d, end is %d\n",start,end);
if(nums[start] > nums[end])
return nums[end];
return nums[start];
}
};
5.搜索旋转排序数组（leetcod 33）
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty())
return -1;
int start = 0, end = nums.size() - 1;
while(start+1 < end)
{
int mid = start + (end - start)/2;
if(target > nums[end])
{
if(nums[mid] > target || nums[mid] <= nums[end])
{
end = mid;
}else if(nums[mid] == target)
{
return mid;
}else
{
start = mid;
}
}
else
{
if(nums[mid] > nums[end] || nums[mid] < target)
{
start = mid;
}else if(nums[mid] == target)
{
return mid;
}else
{
end = mid;
}
}
}
if(nums[start] == target)
{
return start;
}
if(nums[end] == target)
{
return end;
}
return -1;
}
};
6.乘法表中第 k 小的数（leetcod 668）
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int start = 1, end = m*n;
while(start+1 < end)
{
int mid = start + (end - start)/2;
if(count(mid, m, n, k))
{
end = mid;
}
else
{
start = mid;
}
}
if(count(start, m, n, k))
{
return start;
}
return end;
}
private:
bool count(int mid, int m, int n, int k)
{
int res = 0;
for(int i = 1; i <= m; i++)
{
if(mid / i == 0)
{
break;
}
res += min(mid/i,n);
}
return res >=k;
}
};
参考：
1. 一网打尽！二分查找解题模版与题型全面解析
3425
暂无认证
到【灌水乐园】发言
普通网友: 三者的区别呢？值传递、址传递、引用
bql_756272: 好牛，很通透完全看懂了，谢谢🙏
qq_73900979: 因为直接传结构体太大了，而选择传他的地址就八个字节，大多数是选第三种
qq_73900979: 因为直接传结构体太大了，而传他的地址就八个字节
爱于天ding: 你这个全都是错，首先每个图的正极都多了个电阻，计算也都是错