整数二分算法
CPP模板:
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
Python3模板:
def check(x):
#if
def bsearch_1(l, r):
while l < r:
mid = (l + r) >> 1
if check(mid):
r = mid
else:
l = mid + 1
def bsearch_2(l, r):
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
题目:
Leetcode 704.Binary Search
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) >> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
if nums[l] == target:
return l
return -1
LeetCode 69. Sqrt(x)
class Solution:
def mySqrt(self, x: int) -> int:
left = 0
right = x
while left < right:
mid = (left + right + 1) >> 1
if mid * mid <= x:
left = mid
else:
right = mid - 1
return right
LeetCode 34. Find First and Last Position of Element in Sorted Array
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
res = []
if len(nums) == 0 or nums == None:
return [-1, -1]
l = 0
r = len(nums) - 1
while l < r:
mid = (l + r) >> 1
if (nums[mid] >= target):
r = mid
else:
l = mid + 1
if nums[l] is not target:
return [-1, -1]
res.append(l)
l = 0
r = len(nums) - 1
while l < r:
mid = (l + r + 1) >> 1
if (nums[mid] <= target):
l = mid
else:
r = mid - 1
res.append(l)
return res
LeetCode 74. Search a 2D Matrix
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
n = len(matrix)
m = len(matrix[0])
if m == 0 or n == 0:
return False
l, r = 0, m * n - 1
while l < r:
mid = (l + r) >> 1
if matrix[mid // m][mid % m] >= target:
r = mid
else:
l = mid + 1
return matrix[r // m][r % m] == target
CPP
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
//题目考察在2维数组中进行二分操作.
//主要就是如何将2D数组转换为1维数组
//也就是1维数组下标转化为二维
//假设num为要寻找的元素index ==> 二维坐标的位置, [num / m][num % m]. m 为数组每一列的长度
if (matrix.empty() || matrix[0].empty()) return false;
int n = matrix.size(), m = matrix[0].size();
int l = 0, r = n * m - 1;
while (l < r) {
int mid = l + r >> 1;
//寻找mid在二维数组中的位置. mid / m 表示在第几行, mid % m表示在第几个
if (matrix[mid / m][mid % m] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return matrix[r / m][r % m] == target;
}
};
LeetCode 240. Search a 2D Matrix II
class Solution {
public:
//对于这个问题不难发现,对于matrix的右上角的元素来说, 一定满足, 下面的数字比他本身大,
//左边的所有数字, 一定不它小
//所以就利用这个特性, 在搜索的时候,假设x为右上角的元素,
//if x > target -> x下面的数一定不属于target
//if x < target -> x右边的数一定不属于target
//这样每次循环就可以删除一行.
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) {
return false;
}
int i = 0, j = matrix[0].size() - 1;
while (i < matrix.size() && j >= 0) {
int t = matrix[i][j];
if (t == target) return true;
else if(t > target) j --;
else if(t < target) i ++;
}
return false;
}
};
LeetCode 153. Find Minimum in Rotated Sorted Array
CPP
class Solution {
public:
int findMin(vector<int>& nums) {
if (nums[0] < nums.back()) {
return nums[0];
}
int x = nums[0];
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] < x) r = mid;
else l = mid + 1;
}
return nums[l];
}
};
python
class Solution:
def findMin(self, nums: List[int]) -> int:
if nums[0] < nums[-1]:
return nums[0]
x = nums[0]
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) >> 1
if nums[mid] < x:
r = mid
else:
l = mid + 1
return nums[l]
LeetCode 162. Find Peak Element
CPP
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if(nums[mid] > nums[mid + 1]) r = mid;
else l = mid + 1;
}
return l;
}
};
python
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
#由于需要寻找peak的位置, 也就是数组的最高点.
#可以根据相邻两个元素比较来确定, 目前区间中peak的方向.
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[mid + 1]:
right = mid
else:
left = mid + 1
return left
LeetCode 155. Min Stack
LeetCode 496. Next Greater Element I
LeetCode 42. Trapping Rain Water
LeetCode 84. Largest Rectangle in Histogram
LeetCode 475. Heaters
LeetCode 4. Median of Two Sorted Arrays
LeetCode 239. Sliding Window Maximum
LeetCode 456. 132 Pattern