第三章：二分查找基础
二分查找两种写法
闭区间[l, r]
闭区间需要注意的点：
1、当 l = = r 时，区间是有意义的，所以 while(l <= r)
2、更新 r 时，如果 arr[mid] > target，则 mid 不可能是我们要找的数，所以 r = mid – 1。
下面是三种代码实现（其他语言过两天更新）
Java
// 寻找 target 在数组的下标
int find(int[] arr, int target){
int l = 0;
int r = arr.length - 1;//注意点
// l == r 有意义的
while(l <= r){//注意点
//int mid = (l + r) /2;// 存在数值溢出
int mid = l + (r - l) / 2;
if(arr[mid] > target){
r = mid - 1;.// 注意点
} else if(arr[mid] < target){
l = mid + 1;
} else {
return mid;
}
}
}
C++
Python
左闭右开
闭区间需要注意的点：
1、当 l = = r 时，区间是没有意义的，因为 r 不可能是我们要找的数，所以 while(l < r)
2、更新 r 时，r 是不能 r = mid – 1 的，因为 r 不能成为目标数，所以 r = mid;
// 寻找 target 在数组的下标
int find(int[] arr, int target){
int l = 0;
int r = arr.length;
// l == r无意义
while(l < r){
int mid = (l + r) /2;
if(arr[mid] > target){
r = mid;// 不能 r = mid - 1;
}else if(arr[mid] < target){
// 视频中写错了，视频中写成了 l = mid - 1;
l = mid + 1;
}else {
return mid;
}
}
}