一、二分查找概述
二分查找（Binary Search）是一种高效的查找算法，适用于有序数组或列表。（但其实只要满足二段性，就可以使用二分法，本篇博客后面博主会持续更新一些题，来破除一下人们对“只有有序才能二分”的误解。）
二分通过反复将查找范围分为两半，并根据目标值与中间元素的大小关系来确定下一步查找的方向，从而快速定位目标值的位置。
二、二分法习题合集
1.LeetCode 35 搜索插入位置
- 解法
public static int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 使用循环来查找目标值或确定插入位置
while (left <= right) {
int mid = left + (right - left) / 2; // 计算中间位置，避免整数溢出问题
if (nums[mid] > target) {
right = mid - 1; // 如果中间值大于目标值，缩小搜索范围至左半部分
} else if (nums[mid] < target) {
left = mid + 1; // 如果中间值小于目标值，缩小搜索范围至右半部分
} else {
return mid; // 找到目标值，直接返回索引
}
}
// 循环结束时，left 指向应该插入的位置
return left;
}
- 这里博主解释一下为什么最后返回left（debug走一下流程或者在草稿纸上画一画其实就很容易看出来啦~）。
函数 searchInsert 的目标是在给定的有序数组 nums 中查找目标值 target 的插入位置（如果目标值不存在于数组中）。
如果数组中存在目标值，则返回目标值的索引；如果不存在，则返回应该插入的位置索引，使得插入后数组依然保持有序。
插入位置保持有序性：
- 返回
left而不是right是因为当循环结束时，left恰好指向比target大的第一个元素的位置，或者数组的末尾位置（如果target大于数组中的所有元素），这正是目标值应该插入的位置，可以保持数组的有序性。
2.LeetCode 69 x的平方
- 解法
public static int mySqrt(int x) {
if (x == 0 || x == 1) return x;
int left = 0, right = x;
int ans = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
//防止越界~因为 mid*mid 数值过大 int可能会越界 或者 强转一下也可——(long)mid*mid
if (mid < x / mid) { //如果这个整数的平方 严格小于 输入整数，那么这个整数 可能 是我们要找的那个数（重点理解这句话）。
ans = mid;//所以我们更新答案
left = mid + 1;
} else if (mid > x / mid) { //如果这个整数的平方 严格大于 输入整数，那么这个整数 肯定不是 我们要找的那个数；
right = mid - 1;
} else { //如果这个整数的平方 恰好等于 输入整数，那么我们就找到了这个整数；
return mid;
}
}
return ans;
}
3.LeetCode 367 有效的完全平方数
- 解法
public static boolean isPerfectSquare(int num) {
int left = 0, right = num;
// 使用二分查找来确定是否为完全平方数
while (left <= right) {
int mid = left + (right - left) / 2; // 计算中间值，避免整数溢出问题
if ((long) mid * mid < num) {
left = mid + 1; // 如果 mid 的平方小于 num，说明目标值在右半部分，缩小搜索范围至右半部分
} else if ((long) mid * mid > num) {
right = mid - 1; // 如果 mid 的平方大于 num，说明目标值在左半部分，缩小搜索范围至左半部分
} else {
return true; // 如果 mid 的平方等于 num，直接返回 true，表示找到完全平方数
}
}
// 循环结束时，未找到完全平方数，返回 false
return false;
}
4.LeetCode 34 在排序数组查找元素的第一个和最后一个位置
- 解法
本题拆分成两个函数，分别处理较好，不过这个对处理二分的熟练度要求还挺高，比如说left<=right 还是left<right以及左右指针什么时候该怎么移动都有讲究，一个小细节不对的话就得不到正确的答案。
大概的二分的模版大家都知道，区别就在于具体问题的边界问题，是需要自己思考的。
建议有电脑的小伙伴可以debug走一下流程 ，可以看出来左右指针怎么移动的，慢慢调试；或者在纸上画一画，看一看自己写的二分是怎么个流程~
public static int[] searchRange(int[] nums, int target) {
int[] ans = {-1, -1};
// 特殊情况处理：数组为空，或者目标值不在数组范围内
if (nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target) return ans;
// 查找第一次出现的位置
int first = findFirst(nums, target);
if (first == -1) return ans; // 如果找不到目标值，返回初始的{-1, -1}
ans[0] = first;
// 查找最后一次出现的位置
ans[1] = findLast(nums, target);
return ans;
}
// 找到元素第一次出现的位置
public static int findFirst(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1; // 目标值在右半部分
} else if (nums[mid] >= target) {
right = mid - 1; // 目标值在左半部分或者当前位置就是目标值
}
}
// 当退出循环时，left 指向第一个大于等于目标值的位置
return nums[left] == target ? left : -1; // 如果找到目标值，返回该位置；否则返回 -1
}
// 找到元素最后一次出现的位置
public static int findLast(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1; // 目标值在右半部分或者当前位置就是目标值
} else if (nums[mid] > target) {
right = mid - 1; // 目标值在左半部分
}
}
// 当退出循环时，right 指向最后一个小于等于目标值的位置
return right; // 直接返回 right，即最后一次出现的位置
}
5.LeetCode 33 搜索旋转排序数组
- 解法
题目要求我们设计一个时间复杂度为O（logN）的算法，很容易就想到二分法。
但是本题整个数组并不是完全有序的，而是被“旋转”拆分成了两个部分。
如果我们能找到那个旋转点的话，在两个有序的部分进行二分查找就非常轻松了。
那么如果直接遍历数组去找旋转点的话，时间复杂度还是会上升到O（N），不符合题目要求。
我们能不能也用二分去寻找这个旋转点呢？ 答案是可以的。
eg 4 5 6 7 1 2 3——旋转点在 1 处
我们以arr[0]，也就是4为基准，用mid 去跟 arr[0]比较，如果mid>arr[0],说明旋转点在mid右边，如果mid<arr[0],那么可能当前就是旋转点，或者旋转点在右边。
这也算是满足二段性的一个例子了——二分法并不是一定要有序的时候才能用，满足二段性时，也可以使用。
//查找旋转点
public static int findRotationPointIndex(int[] arr) {
// 如果数组长度为2，直接返回较小元素的索引
if (arr.length == 2) return arr[0] < arr[1] ? 0 : 1;
// 初始化左右边界
int left = 0;
int right = arr.length - 1;
// 二分查找旋转点
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= arr[0]) {
left = mid + 1; // mid处于前半段递增序列，旋转点在右半段
} else {
right = mid; // mid处于后半段递增序列或是旋转点
}
}
return left; // left指向旋转点的索引
}
查找到旋转点之后，我们再在两端进行二分查找就比较容易了。
public int search(int[] arr, int target) {
// 如果数组长度为1，直接比较目标值与数组唯一元素
if (arr.length == 1) return target == arr[0] ? 0 : -1;
// 找到旋转点的索引
int index = findRotationPointIndex(arr);
// 初始化左右边界
int left = 0;
int right = arr.length - 1;
// 确定二分查找的范围
if (index == 0) {
// 数组没有旋转，直接在整个数组上执行二分查找
return binaryFind(arr, left, right, target);
}
if (target >= arr[0]) {
right = index; // 目标值可能在旋转点之前（包括旋转点）
} else {
left = index; // 目标值在旋转点之后
}
// 在确定的范围内执行二分查找
return binaryFind(arr, left, right, target);
}
//二分查找
public static int binaryFind(int[] arr, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
6.LeetCode 475 供暖器
- 解法
核心思路就是两句话：
（1）对于每个房屋，要么用前面的暖气，要么用后面的，二者取近的，得到距离；
（2）对于所有的房屋，选择最大的上述距离。
所以我们可以将heaters排好序，然后对每个房屋利用二分法去搜索最近的（相邻的）供暖器即可。
代码实现：
public int findRadius(int[] houses, int[] heaters) {
// 首先对加热器的位置数组进行排序
Arrays.sort(heaters);
// 初始化答案为0
int ans = 0;
int n = houses.length;
// 遍历房屋的位置数组
for (int i = 0; i < n; i++) {
// 对于每个房屋位置，调用二分查找函数找到其最近的加热器，并更新答案
ans = Math.max(binarySearch(heaters, houses[i]), ans);
}
// 返回最大半径
return ans;
}
// 二分查找函数，用于找到距离目标最近的加热器
public int binarySearch(int[] nums, int target) {
int n = nums.length;
// 如果目标大于等于加热器数组中最后一个加热器的位置，直接返回目标与最后一个加热器位置的距离差
if (target >= nums[n - 1]) return target - nums[n - 1];
// 如果目标小于等于加热器数组中第一个加热器的位置，直接返回第一个加热器位置与目标的距离差
if (target <= nums[0]) return nums[0] - target;
// 初始化左右边界
int l = 0, r = n - 1;
// 开始二分查找
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) {
return 0; // 如果找到目标位置，返回距离差为0
} else if (nums[mid] < target) {
l = mid + 1; // 如果目标在当前中间值的右侧，更新左边界
} else {
r = mid - 1; // 如果目标在当前中间值的左侧，更新右边界
}
}
// 循环结束时，l指向的位置即为最终找到的最近的那个比他大的加热器的位置
//取两个差值的最小值
return Math.min(nums[l] - target, target - nums[l - 1]);
}
7.LeetCode 287 寻找重复数
-
这道题博主咋也想不出来能用二分法哈哈哈哈，想破脑壳也找不到二段性
-
但是 还有有二段性滴~ 哈哈哈哈 刚开始看不太明白没关系 博主也琢磨了好一会儿 差点放弃了…
-
自己在纸上找一些例子画一画 慢慢就能get到这个点啦
- 代码实现
public int findDuplicate(int[] nums) {
int len = nums.length; // n + 1 = len, n = len - 1
// 在 [1..n] 查找 nums 中重复的元素
int left = 1;
int right = len - 1;
while (left < right) {
int mid = (left + right) / 2;
// nums 中小于等于 mid 的元素的个数
int count = 0;
for (int num : nums) {
if (num <= mid) {
count++;
}
}
if (count > mid) {
// 下一轮搜索的区间 [left..mid]
right = mid;
} else {
// 下一轮搜索的区间 [mid + 1..right]
left = mid + 1;
}
}
return left;
}
8.LeetCode 74 搜索二维矩阵
- 思路：
1.我们可以通过比较target与每一行的最大值确定目标数字在哪一行。
2.确定在哪一行后直接二分查找即可。
- 解法
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length; // 矩阵的行数
int n = matrix[0].length; // 矩阵的列数
// 如果矩阵只有一行，直接在该行上进行二分查找
if (m == 1) {
return binarySearch(matrix[0], target);
}
int idx = 0;
// 逐行遍历矩阵
while (idx < m) {
// 如果目标值小于等于当前行的最后一个元素，则在当前行中进行二分查找
if (target <= matrix[idx][n - 1]) {
return binarySearch(matrix[idx], target);
}
++idx;
}
// 如果整个矩阵都遍历完仍未找到目标值，则返回 false
return false;
}
private boolean binarySearch(int[] arr, int target) {
int n = arr.length; // 数组的长度
// 如果目标值小于数组第一个元素或大于数组最后一个元素，则直接返回 false
if (target < arr[0] || target > arr[n - 1]) {
return false;
}
int l = 0, r = n - 1;
// 开始二分查找
while (l <= r) {
int mid = l + (r - l) / 2; // 计算中间索引
if (arr[mid] == target) {
return true; // 如果找到目标值，则返回 true
} else if (arr[mid] < target) {
l = mid + 1; // 如果目标值大于中间值，则在右半部分继续查找
} else {
r = mid - 1; // 如果目标值小于中间值，则在左半部分继续查找
}
}
// 如果整个数组都遍历完仍未找到目标值，则返回 false
return false;
}
}
9.LeetCode 240 搜索二维矩阵 ||
同上面一题不同的是，本题行和列都是有序的，那么能不能利用上这个多出来的条件解题呢？
博主想的是对行和列都进行二分查找，然后行列确定target的位置，还实现了代码，但是发现行不通哈哈哈
下面是博主错误的思路
正确的解法：
（1）老老实实的对每一行进行二分查找~
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
if(target < matrix[0][0] || target > matrix[m-1][n-1]) return false;
for(int[] arr:matrix){
if(binaryFind(arr,target)) return true;
}
return false;
}
//二分查找所在行
public boolean binaryFind(int[] arr,int target){
int n = arr.length;
int l = 0,r = n-1;
while(l <= r){
int mid = l + (r-l) / 2;
if(arr[mid]==target){
return true;
}else if(arr[mid]>target){
r = mid -1;
}else{
l = mid +1;
}
}
return false;
}
（2）Z字型查找（从右上角看是一棵二叉搜索树）
把右上角当做二叉搜索树的根，开始搜索，小的往左走，大的往右走
这个方法简直妙不可言… 最快的一集
- 代码实现
//Z字查找 ——当做二叉搜索树
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int i =0,j=n-1;
while(i<m && j>=0){
if(matrix[i][j]==target) return true;
if(matrix[i][j]<target){
++i;
}else{
--j;
}
}
return false;
}
10.LeetCode 81 搜索旋转排序数组 ||
这道题在lc评论区引发了很多争议，很大一部分人认为这解法不是二分，话不多说，直接贴解法吧。
这一题没见过的话，确实不太能够想出来。
class Solution {
public boolean search(int[] nums, int target) {
int n = nums.length; // 数组长度
if (n == 1) {
return nums[0] == target; // 如果数组只有一个元素，直接判断是否等于目标值
}
int l = 0, r = n - 1; // 定义左右指针
while (l <= r) {
int mid = l + (r - l) / 2; // 计算中间位置
if (nums[mid] == target) {
return true; // 找到目标值，返回true
}
// 处理可能的重复元素，缩小搜索范围
if (nums[l] == nums[mid] && nums[r] == nums[mid]) {
++l;
--r;
} else if (nums[l] <= nums[mid]) { // 左半部分有序
if (nums[l] <= target && target < nums[mid]) {
r = mid - 1; // 目标值在左半部分
} else {
l = mid + 1; // 目标值在右半部分
}
} else { // 右半部分有序
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1; // 目标值在右半部分
} else {
r = mid - 1; // 目标值在左半部分
}
}
}
return false; // 没有找到目标值，返回false
}
}
11.LeetCode 153 寻找旋转排序数组中的最小值
- 这道题跟 lc33题搜索旋转排序数组有异曲同工之妙！类似于找旋转点
这里有两种解法:
1.类似于找旋转点，拿mid跟arr【0】比较
public int findMin(int[] nums) {
int n = nums.length; // 数组的长度
if (n == 1) return nums[0]; // 如果数组只有一个元素，直接返回该元素作为最小值
// 如果数组未旋转（即数组第一个元素小于最后一个元素），直接返回第一个元素
if (nums[0] < nums[n - 1]) return nums[0];
int l = 0, r = n - 1; // 初始化左右指针
// 开始二分查找
while (l <= r) {
int mid = l + (r - l) / 2; // 计算中间索引
if (nums[mid] >= nums[0]) {
l = mid + 1; // 如果中间元素大于等于数组第一个元素，则最小元素在右半部分
} else {
r = mid - 1; // 如果中间元素小于数组第一个元素，则最小元素在左半部分
}
}
return nums[l]; // 返回最小元素
}
2.不断更新 每一段有序序列的最小值
class Solution {
public static int findMin(int[] arr) {
int n = arr.length;
if (n == 1) return arr[0]; // 如果数组只有一个元素，直接返回该元素作为最小值
if (arr[0] < arr[n - 1]) return arr[0]; // 如果数组未旋转（即数组第一个元素小于最后一个元素），直接返回第一个元素
int l = 0, r = n - 1; // 初始化左右指针
int min = Integer.MAX_VALUE; // 初始化最小值为整型最大值
while (l < r) {
int mid = (l + r + 1) >> 1; // 计算中间索引
// 如果中间元素大于等于左边界元素，则说明前半部分有序
if (arr[mid] >= arr[l]) {
min = Math.min(min, arr[l]); // 更新最小值为左边界元素和当前最小值的较小值
l = mid; // 将左指针移动到 mid
} else { // 否则，后半部分有序
min = Math.min(min, arr[mid]); // 更新最小值为中间元素和当前最小值的较小值
r = mid - 1; // 将右指针移动到 mid - 1
}
}
return min; // 返回最小元素
}
}
两种解法都可以哈~
12.LeetCode 162 寻找峰值
- 题目要求O（logN），返回任意一个峰值即可，明显二分法呀~
但是固有思维，这里不满足有序怎么二分呢？哈哈哈 ，再一次破除一下二分的思维定式~
只要满足二段性就可以用二分~
- 解法
class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length; // 数组的长度
int l = 0, r = n - 1; // 初始化左右指针
while (l < r) { // 循环直到左指针 l 不小于右指针 r
int mid = l + (r - l) / 2; // 计算中间元素的索引
// 如果中间元素大于其右边的元素，说明峰值可能在左侧或当前位置
if (nums[mid] > nums[mid + 1]) {
r = mid; // 缩小搜索范围到左半部分（包括当前位置）
} else if (nums[mid] < nums[mid + 1]) {
l = mid + 1; // 中间元素小于右边元素，峰值在右半部分
}
}
return l; // 返回峰值元素的索引
}
}
下面趁热打铁，再来一道~
13.LeetCode 1901 寻找峰值 ||
- 这里的峰值，要求行列上都满足，博主最开始的想法是：通过过上一题的解法分别计算出行和列上的峰值，然后看看哪些峰值即满足行也满足列。
- 但是发现好像行不通… 因为你行找的峰值是任意的，有可能对应不上那个列上随意找到的峰值…
- 如果把行列上所有的峰值都找到的话，这才行得通，但是时间复杂度又超了…
错误示范：
class Solution {
public int[] findPeakGrid(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[] ans = new int[2];
Set<String> set = new HashSet<>();
// 寻找每一行的峰值
for (int i = 0; i < m; i++) {
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r-l) /2;
if(mat[i][mid]>mat[i][mid+1]){
r = mid;
}else if(mat[i][mid]<mat[i][mid+1]){
l = mid + 1;
}
}
set.add(i+","+l);
}
//寻找每一列的峰值
for(int i=0;i<n;i++){
int l=0,r = m-1;
while(l<r){
int mid = l + (r-l)/2;
if(mat[mid][i]>mat[mid+1][i]){
r = mid;
}else if(mat[mid][i]<mat[mid+1][i]){
l = mid + 1;
}
}
if(set.contains(l+","+i)){
ans[0] =l;
ans[1] = i;
return ans;
}
}
return ans;
}
}
- 然后我换了一个思路就是…
- 找行峰值的时候找到了，去判断一下上下位置是否满足，如果满足就直接返回
- 找列峰值的时候找到了，去判断一下左右位置是否满足，如果满足就直接返回
- 写着写着感觉这样写的是不是有漏洞… 但是还是过了
class Solution {
public int[] findPeakGrid(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[] ans = new int[2];
// 寻找每一行的峰值
for (int i = 0; i < m; i++) {
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (mat[i][mid] > mat[i][mid + 1]) {
r = mid;
} else {
l = mid + 1;
}
}
// 检查是否为峰值
boolean up = (i == 0 || mat[i][l] > mat[i - 1][l]);
boolean down = (i == m - 1 || mat[i][l] > mat[i + 1][l]);
if (up && down) {
ans[0] = i;
ans[1] = l;
return ans;
}
}
// 寻找每一列的峰值
for (int i = 0; i < n; i++) {
int l = 0, r = m - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (mat[mid][i] > mat[mid + 1][i]) {
r = mid;
} else {
l = mid + 1;
}
}
// 检查是否为峰值
boolean left = (i == 0 || mat[l][i] > mat[l][i - 1]);
boolean right = (i == n - 1 || mat[l][i] > mat[l][i + 1]);
if (left && right) {
ans[0] = l;
ans[1] = i;
return ans;
}
}
return ans;
}
}
- 给一个贴一个更加严谨的解法吧~
更新于：
