二分查找
模板题 704. 二分查找
二分查找是一种效率较高的方法(logN) , 它的要求是线性表中元素是有序的
我们常见的写法有：
public int binarySearch(int[] nums , int target){
int left = 0 , right = nums.length - 1;
while(left <= right){
//left > right则退出，此时搜索区间为[left , right]
int mid = left + (right - left) / 2;//(left + right) / 2
if (nums[mid] == target){
return mid;
}else if (nums[mid] > target){
right = mid - 1;
}else if (nums[mid] < target){
left = mid + 1;
}
}
return -1;
}
另一种写法：
public int binarySearch(int[] nums , int target){
int left = 0 , right = nums.length;
while(left < right){//difference
//left == right则退出，此时搜索区间为[left , right)
int mid = left + (right - left) / 2;
if (nums[mid] == target){
return mid;
}else if (nums[mid] > target){
right = mid;
}else if (nums[mid] < target){
left = mid + 1;
}
}
return -1;
}
从两种写法中，我们可以得知有两个不同：循环条件的退出以及搜索区间，这是二分查找的易错点。
边界问题没处理好导致死循环，搜索区间没处理好则把结果去除了。
二分查找的另一种用法，搜索左右边界
模板题 34. 在排序数组中查找元素的第一个和最后一个位置
通常我是把左右边界分开写，因为我怕逻辑出错导致WA，这里我用的是[Left , Right]去寻找左右边界。
而我们需要思考在什么时候更新下一个搜索区间，才可以逼近左/右边界
- 寻找左边界
- nums[mid] > target , 此时说明未找到target，缩小区间
- nums[mid] == target , 此时说明找到target，更新right ，但没有确定是不是边界
- 寻找右边界
- 同理，我们在nums[mid] == target的时候更新left
第一种写法[left , right]
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) return new int[]{-1, -1};
int lower = lowerBound(nums, target);
int upper = upperBound(nums, target);
return new int[]{lower, upper};
}
private int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {//1.
right = mid - 1;
} else {
left = mid + 1;
}
}
if (left >= nums.length || nums[left] != target) {//检查元素是否符合
return -1;
}
return left;
}
private int upperBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {//2.
left = mid + 1;
} else {
right = mid - 1;
}
}
if (right < 0 || nums[right] != target) {//检查元素是否符合
return -1;
}
return right;
}
第二种写法[left , right)
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) return new int[]{-1, -1};
int upper = upper(nums, target);
int lower = lower(nums, target);
return new int[]{lower, upper};
}
private int lower(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
private int upper(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
if (left == 0 || nums[left - 1] != target) return -1;
return left - 1;//return right
}