前言
别直接背模板，要理解记忆
- 二分查找的基本思想：[
减而治之] 每次都将问题的规模减少，直到问题解决
”开胃菜“：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;
}
}
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于