二分查找
通用解题模板：
区间定义：[l, r) 左闭右开
-
f(m)函数满足该条件，可直接返回对应位置 -
g(m)函数满足该条件，可移动右边界 - 同理，在else中移动左边界
- 如果没有这个条件的判断就是
lowwer_bound和higher_bound.
def binary_search(l, r):
while l < r:
m = l + (r - l) // 2
if f(m): # 判断找了没有，optional
return m
if g(m):
r = m # new range [l, m)
else:
l = m + 1 # new range [m+1, r)
return l # or not found
lower bound: find index of i, such that A[i] >= x
def lowwer_bound(self, nums, target):
# find in range [left, right)
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) / 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
upper bound: find index of i, such that A[i] > x
def higher_bound(self, nums, target):
# find in range [left, right)
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) / 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
return left
例题
- 题目 69. x 的平方根
几个坑点
- 对于输入参数的判断，可以先处理
- right 不能随便+1，有可能溢出 int 或者 long的长度
- 平方需要用的结果需要转long，防止溢出 int
示例代码java
class Solution {
public int mySqrt(int x) {
if (x<2)
return x;
int left = 0;
// x 一定大于 x/2
int right = x/2+1;
while (left<right) {
// 这个是需要注意的点，平放有可能会超出int范围
int mid = left+(right-left)/2;
long num = (long)mid * mid;
if (num==x)
return mid;
if (num>x)
right=mid;
else
left=mid+1;
}
return left-1;
}
}
解题思路
- 对于有边界的题，需要考虑左边界和有边界
对于 letf right +-1 的说明 可参考
示例代码
class Solution {
public int[] searchRange(int[] nums, int target) {
int len = nums.length;
int[] res = new int[]{-1,-1};
int left =0;
int right = len;
// 先找左边界
while (left<right){
int mid = left+(right-left)/2;
if (nums[mid] == target)
res[0] = mid;
if (nums[mid]>=target) {
right = mid;
}
else
left = mid+1;
}
// 先找右边界
right = len;
while (left<right){
int mid = left+(right-left)/2;
if (nums[mid] == target)
res[1] = mid;
if (nums[mid]<=target) {
left = mid+1;
}
else
right = mid;
}
return res;
}
}
参考视频
- 花花酱的二分查找专题视频：https://www.youtube.com/watch?v=v57lNF2mb_s
