先用leetcode专题进行练习. 只要遇到了排了序的数组, 实际上都可以考虑能否用二分法加速.
704. 二分查找
首先做最基本的二分查找.
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (right + left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
}
return -1;
}
}
可以发现一共有三步:
- 预处理 — 如果集合未排序,则进行排序
- 二分查找 — 使用循环或递归在每次比较后将查找空间划分为两半
- 后处理 — 在剩余空间中确定可行的候选者
leetcode给出了三个模板, 我们分别练习. 我稍微修改了模板的源码, 更加符合我的思路.
模板1
- 初始条件: left = 0, right = length - 1
- 终止: left > right
- 向左查找: right = mid - 1
- 向右查找: left = mid + 1
最基础的模板
int binarySearch(int[] nums, int target){
if (nums == null || nums.length == 0) return -1;
int left = 0, right = nums.length - 1;
while(left <= right){
int mid = (right + left) / 2; //等价于left + (right - left) / 2, 后者不会越界
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
}
return -1;
}
69. x的平方根
mid平方后可能超出int范围, 所以用long转个类型.
class Solution {
public int mySqrt(int x) {
int left = 0, right = x;
int res = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (mid * mid == x) {
return mid;
} else if ((long)mid * mid < x) {
res = mid;
left = mid + 1;
} else if ((long)mid * mid > x) {
right = mid - 1;
}
}
return res;
}
}
374. 猜数字大小
注意不要越界.
public class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 1, right = n;
while (left <= right) {
int mid = left + (right - left) / 2; //这样写才不会越界
// 或者 int mid = (int)(((long)left + (long)right) / 2);
int res = guess(mid);
if (res == 0) {
return mid;
}
else if (res == 1) left = mid + 1;
else if (res == -1) right = mid - 1;
}
return -1;
}
}
33. 搜索旋转排序数组
首先要知道无旋转的范围, 再判断target是否在无旋转的范围内, 否则就在另一边.
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[0] <= nums[mid]) { //0到mid无旋转
if (target < nums[mid] && target >= nums[0]) right = mid - 1; //target在左边较大的有序范围内
else left = mid + 1;
} else if (nums[0] > nums[mid]) { //mid到后面无旋转
if (target > nums[mid] && target <= nums[nums.length - 1]) left = mid + 1; //target在右边较小的有序范围内
else right = mid - 1;
}
}
return -1;
}
}
模板II
- 初始条件: left = 0, right = length
- 终止: left == right
- 向左查找: right = mid
- 向右查找: left = mid + 1
right的条件变了, while中的判断等号没有了.
int binarySearch(int[] nums, int target) {
if(nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length;
while(left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid;
}
if (left != nums.length && nums[left] == target) return left;
return -1;
}
278. 第一个错误的版本
正确答案可能也包含right自身, 所以不能让right = mid - 1.
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid) == false) left = mid + 1;
else right = mid; //自身也可能是答案
}
return left; //right也行
}
}
162. 寻找峰值
left到不了右边, 所以mid + 1永远在数组的index范围内.
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left; //right也行
}
}
153. 寻找旋转排序数组中的最小值/154. 寻找旋转排序数组中的最小值II/剑指Offer11. 旋转数组的最小数字
注意154中有重复值, 也有可能没有旋转, 所以最好就是用right去比较. 如果相等的话, 用left比较就不知道到底在哪边了.
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[right] < nums[mid]) left = mid + 1;
else if (nums[right] > nums[mid]) right = mid;
else right--;
}
return nums[left];
}
}
模板三
- 初始条件: left = 0, right = length - 1
- 终止: left + 1 == right
- 向左查找: right = mid
- 向右查找: left = mid
每一步有三个元素, 最后也会剩下两个元素.
int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int left = 0, right = nums.length - 1;
while (left + 1 < right){
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
34. 在排序数组中查找元素的第一个和最后一个位置
我这个似乎不是模板三的做法, 怎么用模板三思想一步搞定呢?. 注意右边界要取上界, 所以要加1. 思考[1, 2, 2, 3]的情况, $0 + 3 / 2$永远不大于1, 右边界就找不到了.
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) return new int[]{-1, -1};
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
int l = left;
left = 0;
right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2 + 1; // 右边界要取上界, 所以这里加1
if (nums[mid] > target) right = mid - 1;
else left = mid;
}
if (nums[l] != target) return new int[]{-1, -1};
return new int[]{l, right};
}
}
要包含上界记得计算mid整除的时候加1
658. 找到K个最接近的元素
其实就是去找窗口大小为k的, 这些窗口的左边界.
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int left = 0, right = arr.length - k - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (x - arr[mid] > arr[mid + k] - x) { //左边离x远, 向右靠近
left = mid + 1;
} else {
right = mid - 1;
}
}
List<Integer> res = new LinkedList<>();
for (int i = left; i < left + k; i++) {
res.add(arr[i]);
}
return res;
}
}
287. 寻找重复数
通过count来查找有重复数组的范围, left/right/mid这些数字不仅是指针, 也是我们猜测的数.
class Solution {
public int findDuplicate(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = (right - left) / 2 + left;
int count = 0;
for (int num : nums) {
if (num <= mid) {
count += 1;
}
}
if (count > mid) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
其他题
875. 爱吃香蕉的珂珂
这道题的启发是, 当我们遇到顺序遍历的时候, 都可以想一下能否用二分法加速. 这一道题顺序遍历会超时, 自然就想到用二分法缩短时间. 这里的left和right指的就是速度.
class Solution {
public int minEatingSpeed(int[] piles, int H) {
int max = getMax(piles);
/*
for (int i = 1; i < max; i++) {
if (canFinish(piles, i, H)) return i;
}
return max;
*/
//顺序的遍历就可以用二分法代替
int left = 1, right = max + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(piles, mid, H)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private int getMax(int[] arr) {
int max = -1;
for (int num: arr) {
max = Math.max(num, max);
}
return max;
}
private boolean canFinish(int[] piles, int speed, int H) {
for (int n: piles) {
H -= (n / speed) + (((n % speed) > 0) ? 1 : 0);
if (H < 0) return false;
}
return true;
}
}
1011. 在D天内送达包裹的能力
同上, 本来是需要暴力法去搜索最低运载能力, 也就是从1到整个weights之和, 因为是递增的数列, 那么实际上就可以用二分法.
class Solution {
public int shipWithinDays(int[] weights, int D) {
int left = 1, right = 0;
for (int num : weights) {
right += num;
}
right++;
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(weights, D, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
boolean canFinish(int[] weights, int D, int weight) {
int j = 0;
for (int i = 0; i < D; i++) { //天数
int w = weight; //假设的最低装载量
while ((w -= weights[j]) >= 0) { //还有剩余则继续装下一个, 没有剩余就放到第二天装
j++;
if (j >= weights.length) return true;
}
}
return false;
}
}
参考
comments powered by Disqus