4种二分查找模版讲解
视频讲解链接：【二分查找模版】四种变形的二分查找
实现代码看这里
package sort;
public class BanarySort {
public static void main(String[] args) {
int[] arr = new int[]{1, 2,3,3,3,4,5,5,7};
int target = 3;
int index = floor_lower(arr, target);
System.out.println("index = "+ index + ", value = " + arr[index]);
}
//1.寻找第一个大于 target 的元素的下标，案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
public static int upper(int[] arr, int target){
// 二分查找需要想清楚的点
int l = 0;
int r = arr.length - 1;
// 判断特殊情况
if(arr[r] <= target){
return -1;
}
//[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
while(l < r){
int mid = (r - l) / 2 + l;
if(arr[mid] > target){
//[l ,mid, r]
r = mid;
} else if(arr[mid] == target){
l = mid + 1;
}else {//arr[mid] < target
l = mid + 1;
}
}
return l;
}
//2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
// 如果不存在，则返回第一个大于 target 的元素下标
//案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
public static int floor_upper(int[] arr, int target){
int l = 0;
int r = arr.length - 1;
// 判断特殊情况
if(arr[r] < target){
return -1;
}
//[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
while(l < r){
int mid = (r - l) / 2 + l;
if(arr[mid] > target){
//[l ,mid, r]
r = mid;
} else if(arr[mid] == target){
l = mid + 1;
}else {//arr[mid] < target
l = mid + 1;
}
}
if(l - 1 >= 0 && arr[l - 1] == target){
return l -1;
}
return l;
}
//3.寻找最后一个小于 target 的元素的下标
// [1, 2,3,3,3,4,5,5,7],target = 3;
public static int lower(int[] arr, int target){
int l = 0;
int r = arr.length - 1;
// 判断特殊情况
if(arr[l] >= target){
return -1;
}
//[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
while(l < r){
// r = 1,l = 0,mid = 0
int mid = (r - l + 1) / 2 + l;
if(arr[mid] > target){
//[l ,mid, r]
r = mid - 1;
} else if(arr[mid] == target){
r = mid - 1;
}else {//arr[mid] < target
l = mid;
}
}
//
return l;
}
// 4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，
// 如果不存在，则返回最后一个小于 target 的元素的下标
//[1, 2,3,3,3,4,5,5,7],target = 3;
public static int floor_lower(int[] arr, int target){
int l = 0;
int r = arr.length - 1;
// 判断特殊情况
if(arr[l] > target){
return -1;
}
//[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
while(l < r){
// r = 1,l = 0,mid = 0
int mid = (r - l + 1) / 2 + l;
if(arr[mid] > target){
//[l ,mid, r]
r = mid - 1;
} else if(arr[mid] == target){
r = mid - 1;
}else {//arr[mid] < target
l = mid;
}
}
//
if(l + 1 < arr.length && arr[l + 1] == target){
return l + 1;
}
return l;
}
}