简单的二分查找
前提:数组有序(可先排序),无重复数组(可单独处理)
1. 一般使用左闭右开区间,感觉代码容易一点点,不要记太多的套路,直接一套带走,左闭右开
2. 二分查找特别需要注意左右的区间: 这里很容易写错,所以最好的办法是在纸上画一个数组,要记住边界的限定,时刻在心中默念,左闭右开无等号,有闭有加,无闭无加
while (left < right)//无等号left = mid + 1;//左闭right = mid; //右开
3. 最后一点就是middle的值了,这里需要注意一点的就是,防止超出int类型的最大值,只需要记住,防超出用减号:
int mid = left + ((right - left) / 2)
左闭右闭:
-
while(left <= right), 因为当left == right 的时候是有意义的
-
if(nums[middle] > target), right要赋值为middle-1,因为当前这个nums[middle] 一定不是target,那么接下来要查找的左右区间结束下标位置就是middle-1
代码:左闭右闭区间
左闭右开:[left, right)
class Solution {
public int search(int[] nums, int target) {
// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1; //左闭右闭
}
return -1;
}
}
-
while(left < right), 使用<, 因为left==right在区间中是没有意义的
-
if(nums[midlle] > target), right 更新为middle, 因为当前nums[middle]不等于target, 去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle, 即:下一个查询区间不会去比较nums[middle]
代码:左闭右开区间
class Solution { public int search(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) {//左闭右开区间 int mid = left + ((right - left) >> 1); if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid; //左闭右开区间 } return -1; } }