🎉二分查找详解+剑指offer经典试题
文章目录
前言：
排序数组中的搜索问题，首先想到 二分法 解决。二分查找法在面试中出现的频率很高，希望这篇文章能够对你有所帮助，祝你我万千人中，取得满意的offer
二分查找
简介
二分查找需要的条件
- 用于查找内容逻辑上来说是需要
有序的 - 查找的数量只有是
一个，而不是多个
在二分查找中，目标元素的
查找区间的定义十分重要，不同的区间的定义写法不同
因为查找的区间是不断迭代的，所以确定查找的范围十分重要，主要有以下两种方式:
- 左闭右闭
[left,right] - 左闭右开
[left,right)
通过一个例子来更好的理解不同方式的不同写法：
题目如下：
给定一个 n 个元素
有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
这道题的思想很简单，因为整个数组是有序的，数组默认是递增的。
- 首先选择
数组中间的数字和需要查找的目标值进行比较 - 如果相等，直接返回答案
- 如果不想等
- 如果
中间的数字大于目标值，则直接排除以中间数字向右的数字 - 如果
中间的数字小于目标值，则直接排除以中间数字向左的数字 - 总之一句话，目标值在哪边就保留哪一边
- 如果
在这里，我想很多友友们对 数组长度不是奇数时，如何取半有疑惑，其实一开始我也是有的（哈哈哈，当时一直都不很疑惑），这里我给大家在梳理一下
当数组长度为为奇数时：
是奇数的情况很简单，如果需要查找的数字是29，因为29大于中间的数字（11），所以左边的数字全部排除，只看右边的就行
当数组长度为偶数时：
第一种写法（左闭右闭）
二分查找最重要的两个点：
- while循环中 left 和 right 的关系，到底是
left <= right，还是 left < right - 迭代过程中 middle 和 right 的关系，到底是
right = middle -1 还是 right = middle
对于第一种写法：每次查找的区间在[left,right]，根据查找区间的定义，就决定了后续代码如何编写。因为 target 在[left，right] 区间，所以有以下两点
- 循环条件要是用
while(left <= right)，因为当（left == right）这种情况发生的时候，得到的结果是有意义的。 if(nums[middle] > target)，right 要赋值为 middle -1，因为当前的 nums[middle] 一定不是 target，需要把这个middle 位置上面的数字丢弃，那么接下来需要查找的范围就是[left,middle-1]
接下来我们分析这个示例的解题思路：
首先看一个数组，需要对这个数组进行操作。需要对33进行查找的操作，那么target的值就是33
- 首先，对 left 的值 和 right 的值 进行初始化，然后计算 middle 的值
- left = 0，right = size -1
- middle = （left + （right - left）/ 2）
- 比较 nums[middle]的值和 target 的值的大小关系
- if(nums[middle] > target),说明 middle 向右的所有数字大于 target
- if(nums[middle] < target),说明 middle 向左的所有数字小于 target
- nums[middle] = 13 < target = 33,left = middle + 1
如下图：
- 循环条件为 while （left <= right）
- 此时，left = 6 <= right = 11,则继续进行循环
- 当前，middle = left + ((right - left) / 2),计算出 middle 的值
- 计算出 middle 的值后，比较 nums[middle] 和 target 此时 nums[middle] = 33 = target = 33，找到目标
代码如下：
class N {
public int search(int nums[], int size, int target) {
// 初始化 left 和 right
int left = 0 ;
int right = size - 1;// size 为数组大小
// 左闭 右闭
while (left <= right) {
// 先找到 middle 的大小
int middle = left + (right - left)/2;
if(nums[middle] > target) {
right = middle - 1;//target 在区间[left，middle-1]
// 因为middle肯定不等于target，middle要舍弃
}else if(nums[middle] < target) {
left = middle + 1;// target 在区间[middle+1,right]
}else {// 既不在左也不在右，刚好就在中间
return middle;
}
}
// 没有找到目标
return -1;
}
}
第二种写法（左闭右开）
第二种写法，每次查找的区间在[left，right）左闭右开区间，根据定义，条件控制如下
- 循环条件不是 while（left <= right）而是
（left < right） - if(nums[middle] > target) ,right = middle ,因为当前 nums[middle] 是大于 target 的，不符合条件，不能取到middle，并且区间的定义[left，right），刚好区间上的定义就取不到right，所以right赋值为middle
如下图：
-
第一步还是初始化 left 和 right 的值，然后计算 middle 的值
- left = 0，right = size
- 循环条件 while（left < right）
-
因为是左闭右开区间，所以数组定义如下：
- 计算 middle 的值：
- 比较 nums[middle] 和 target 的大小：因为 nums[middle] = 22 > target = 3
- 所以 right = middle
- 符合循环的条件，接着计算 middle 的值
- 比较nums[middle] 和 target 的大小，因为 nums[middle] = 9 > target = 3
- 所以 right = middle
- 符合循环的条件，继续计算middle的值
- 比较 nums[middle] 和 target 的大小关系：因为 nums[middle] = 0 < target = 3
- 所以 left = middle + 1
- 符合循环条件，接着计算 middle 的值
- 比价 nums[middle] 和 target 的关系，nums[middle] = 3 =target = 3
- 成功找到 target
代码如下:
int search(int nums[], int size, int target)
{
int left = 0;
int right = size; //定义target在左闭右开的区间里，即[left, right)
while (left < right) { //因为left = right的时候，在[left, right)区间上无意义
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle; //target 在左区间，在[left, middle)中
} else if (nums[middle] < target) {
left = middle + 1;
} else {
return middle;
}
}
// 没找到就返回-1
return -1;
}
二分查找我们理清楚了，后面的题也就引刃而解
剑指 Offer 53 - I. 在排序数组中查找数字 I
这道题我扫了遍题目过后，我首先想到的是循环遍历，当然这种暴力的做法在面试中是不可取的，还是一句话，排序数组中搜索问题，首先想到二分查找这道题方法极多，以下方法仅供参考，若有错误，欢迎指出
方法一：暴力递归
这种方法面试笔试不可取，如果实在是想不到的情况下，可以用 ^^
class Solution {
public int search(int[] nums, int target) {
int count = 0;//记录次数
for(int i = 0;i < nums.length;i++) {
if(nums[i] == target) {
count++;
}
}
return count;
}
}
方法二：双二分
二分查找找最容易出错的就是边界条件，二分实质不难，但是容易出错，需要细心
- 先找到 target 第一次出现的位置（下标）：firstPosition
- 再找到 target 第二次出现的位置（下标）：lastPosition
- 两者之差再加 1 （lastPosition - firstPosition + 1）就是 target 出现的次数
class Solution {
public int search(int[] nums, int target) {
// 双二分查找 去找第一次出现和最后一次出现的位置
int len = nums.length;
if(len == 0) {
return 0;
}
// 第一次出现的位置（下标）
int firstPosition = findFirstPosition(nums,target);
if(firstPosition == -1) {// 如果没有出现返回0
return 0;
}
int lastPosition = findLastPosition(nums,target);
// 最后一次出现的位置 - 第一出现的位置 + 1 = target 出现的次数
return lastPosition - firstPosition + 1;
}
// 第一次二分找到第一次出现的位置
public int findFirstPosition(int[] nums,int target) {
// 初始化 left 和 right
int left = 0;
int right = nums.length - 1;
// 当 left 和 right 重合时 退出循环
while(left < right) {
int mid = left + (right - left) / 2;// 找到中中间值
// 1. 如果 中间值 小于 target
if(nums[mid] < target) {
// 说明第一次出现的位置肯定在 mid 的右边[mid+1,right];
left = mid+1;
}else if(nums[mid] == target) {
// 如果 等于 target,第一次出现的位置,可能是mid，也可能是mid前面[left,mid]
right = mid;
}else {
// 如果 大于 target，第一次出现的位置应该在 [left，mid-1]
right = mid - 1;
}
}
// 如果 left 刚好 等于 target
if(nums[left] == target) {
return left;
}
return -1;
}
// 第二次二分 找到最后一次出现的位置
public int findLastPosition(int[] nums,int target) {
int left = 0;
int right = nums.length - 1;
while(left < right) {
// 取 mid + 1 是为了避免死循环，在待搜索区间只要有 2 个元素的时候，
//mid = (left + right) >>> 1 只能取到左边那个元素，如果此时边界设置是 left = mid ，
//区间分不开，因此要改变下取整的行为，在括号里加 1 变成上取整。
int mid = left + (right - left + 1) / 2;
if(nums[mid] <= target) {
// [mid,right]
left = mid;
}else {
// nums[mid] > target
// [left... mid-1]
right = mid -1;
}
}
return left;
}
}
剑指 Offer 53 - II. 0～n-1中缺失的数字
排序数组中的搜索问题，首先想到 二分法 解决
扫了一遍题目，有序且增序，找出有且只有一个的数，满足二分查找的条件，毫无疑问这道题采用二分查找法，方法有很多，以下仅供参考，若有错误欢迎指出
方法一（二分查找）：
- 初始化：左边界 left = 0 ，右边界 nums.length -1 代表闭区间[left，right]
- 循环二分：
- 若
nums[mid] = mid，则 所找元素一定在[mid+1，right] - 若
nums[mid] 不等于 mid，则 所找元素 一定在[left，mid-1]
- 若
- 返回值：
left
class Solution {
public int missingNumber(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left)/2;
if(nums[mid]==mid) {
left = mid + 1;
}else {
right = mid - 1;
}
}
return left;
}
}
方法二（暴力法）：
遍历数组，只要比较数组下标和改下标对应的值即可，如果都对应返回最后一项即可
class Solution {
public int missingNumber(int[] nums) {
for(int i = 0;i < nums.length;i++) {
if(nums[i] != i) {
return i;
}
}
return nums.length;
}
}
剑指 Offer 03. 数组中重复的数字
题目说不需要知道数字出现了多少次，只需要找到重复的数字，我们不妨考虑HashSet（自带去重操作），遍历数组，如果set已经存在相同元素，直接返回
class Solution {
public int findRepeatNumber(int[] nums) {
// 注意这里不是用 HashMaP而是 HashSet 原因是 set 自带去重操作
Set<Integer> set = new HashSet<>();
for(int n : nums) {
if(set.contains(n)) {
return n;
}else {
set.add(n);
}
}
return -1;
}
}
剑指 Offer 04.二维数组中的查找
由于给定的二维数组具备每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。
从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。
证明：可以证明这种方法不会错过目标值。如果当前元素大于目标值，说明当前元素的下边的所有元素都一定大于目标值，因此往下查找不可能找到目标值，往左查找可能找到目标值。如果当前元素小于目标值，说明当前元素的左边的所有元素都一定小于目标值，因此往左查找不可能找到目标值，往下查找可能找到目标值。
方法一：
代码如下：
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
// 初始化 i,j
int i = matrix.length - 1;
int j = 0;
// 边界条件
while(i >= 0 && j < matrix[0].length) {
if(matrix[i][j] > target) {
i--;
}else if(matrix[i][j] < target) {
j++;
}else {
return true;
}
}
return false;
}
}
方法二（暴力递归）：
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
// 暴力递归法
// 递归终止条件
if(matrix == null || matrix.length ==0 || matrix[0].length == 0) {
return false;
}
for(int i = 0;i < matrix.length;i++){
for(int j = 0;j < matrix[0].length;j++){
if(matrix[i][j] == target) {
return true;
}
}
}
return false;
}
}
剑指 Offer 11. 旋转数组的最小数字
方法一（二分查找）：
借用力扣一大佬的解题思路：由图中示例可得，旋转点为这组数据中的最小值
具体讲解：力扣
-
初始化：left 和 right 指针 分别指向 数组的左右两端
-
循环二分：
- 当
nums[mid]>nums[right] 时： 最小值 一定在 左排序数组 中，即旋转点 一定在 [mid + 1, j] 闭区间内，因此执行 i = m + 1； 当 nums[mid] < nums[j] 时：最小值 一定在 右排序数组 中，即旋转点 一定在[left, mid][闭区间内，因此执行 right= mid；当 nums[mid] = nums[right] 时： 无法判断 最小值 在哪个排序数组中，即无法判断旋转点 在 [left, mid] 还是 [mid + 1, right] 区间中。解决方案： 执行 right = right -1缩小判断范围
- 当
-
返回值：当
left = right 时跳出二分循环，并返回 旋转点的值nums[left]即可。
代码如下：
class Solution {
public int minArray(int[] numbers) {
int left = 0;
int right = numbers.length-1;
while(left < right) {
int mid = left + (right - left)/2;
if(numbers[mid] > numbers[right]) {
left = mid + 1;
}else if(numbers[mid] < numbers[right]) {
right = mid;
}else {
right--;
}
}
return numbers[left];
}
}
总结
“种一颗树最好的是十年前,其次就是现在”
所以,
“让我们一起努力吧,去奔赴更高更远的山海”
如果有错误?,欢迎指正哟😋
🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉
