leetcode解题模板 —— 二分查找-爱代码爱编程
1.模板
vector<int>& nums
int left = 0;//左边界
int right = nums.size()-1;//右边界
int mid = 0;
while(left <= right) {
mid = (left + right) / 2;
if(target == nums[mid]) {/*操作*/ }
if(target < nums[mid]) {
right = mid-1;
}
else {
left = mid+1;
}
}
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.size() == 0) return 0;
int left = 0;
int right = nums.size()-1;
if(nums[left] >= target) {return 0;}
if(nums[right] < target) {return nums.size();}
int mid = 0;
while(left <= right) {
mid = (left + right) / 2;
if(target == nums[mid]) { return mid;}
if(target < nums[mid]) {
right = mid-1;
}
else {
left = mid+1;
}
}
return left;
}
};
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size() == 0 || matrix[0].size() == 0) {return false;}
int n = matrix[0].size()-1;
int m = matrix.size()-1;
if(matrix[0][0] > target || matrix[m][n] < target) {return false;}
int left = 0;
int right = m;
int mid = 0;
while(left <= right) {
mid = (left + right) / 2;
if(matrix[mid][0] == target) {return true;}
if(target < matrix[mid][0]){
right = mid -1;
}
else {
left = mid + 1;
}
}
int a = left-1;
left = 0;
right = n;
while(left <= right) {
mid = (left + right) / 2;
if(matrix[a][mid] == target) {return true;}
if(target < matrix[a][mid]){
right = mid -1;
}
else {
left = mid + 1;
}
}
return false;
}
};
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
if(grid.size() == 0 || grid[0].size() == 0) {
return 0;
}
int m = grid.size() - 1;
int n = grid[0].size() - 1;
int ans = 0;
for(int i = 0; i <= m; i++) {
if(grid[i][0] < 0) {
ans += n + 1;
continue;
}
if(grid[i][n] >= 0) {continue;}
int left = 0;
int right = n;
int mid = 0;
while(left < right) {
mid = (left + right) / 2;
if(grid[i][mid] == 0) {
while(mid + 1 <= n && grid[i][mid + 1] == 0) {mid++;}
left = mid +1;
}
if(grid[i][mid] > 0) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
if(grid[i][left]<0){
ans += n - left + 1;
}else {
ans += n - left;
}
}
return ans;
}
};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/Hu_weichen/article/details/111092970