前言
别直接背模板,要理解记忆
- 二分查找的基本思想:[
减而治之
] 每次都将问题的规模减少,直到问题解决
”开胃菜“:LeetCode 1095 山脉数组中查找目标值
重点:二分查找两种思路:
- 思路 1:在循环体内部查找元素:
while (left <= right)
;- 思路 2:在循环体内部排除元素:
while (left < right)
。
关于二分查找我想说
-
防止整型溢出求中点的写法:
mid = left + (right - left) / 2
-
二分查找类问题中上取整和下取整的问题。这里我给大家举个例子:给一个数组 [1 ,2] 正常来说我们求中点位置的计算方法是 mid = (left + right)/ 2,这样计算得到的中点位置的下标是 0 对应上面数组中的 1 ,这是向下取整,当我们见到 left = mid 的时候,这时候我们都是使用向上取整,也就是 mid = (left + right + 1)/ 2 这种写法,因为只有这样我们的 mid 才能落在后面。具体细节建议大家 debug 去分析。
-
每次做完判断就要明确自己的下一步落点区间实在什么位置,不要死记硬背模板!
-
二分查找中,我们常见的数组是升序 ,并且元素是不重复的,但是我们同样会遇到那种元素重复的题。例如:LeetCode 81. 搜索旋转排序数组 II 、 LeetCode 154. 寻找旋转排序数组中的最小值 II 里面给的数组虽然是升序或者降序排序,但是里面的元素是重复的,这时候我们就要去重,这里给大家一个简单的去重方法,大家只需要在之前的判断基础上加上以下代码 👇👇👇👇
if(nums[left] == nums[mid] && nums[mid] == nums[right]) { ++left; --right; }
- 在二分查找这一章节中,我给大家的建议是多刷题,弄清楚每一步的原因。
- 二分查找题我个人认为是细节魔鬼,搞懂其中的细节,二分查找题不在话下!
LeetCode 二分查找类型
704. 二分查找
- 代码
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
if(len == 0){
return -1;
}
int left = 0;
int right = len-1;
int mid = left+(right - left)/2;
while(left <= right){
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
}
mid = left+(right - left)/2;
}
return -1;
}
}
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于