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;
}
}
评论(1)
int upper(vector<int>& arr, int target){
int l = 0;
int r = arr.size() - 1;
if (arr[r] <= target)
{
return -1;
}
int res = 0;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (arr[mid] > target)
{
r = mid - 1;
res = mid;
}
else
{
l = mid + 1;
}
}
return res;
}
//如果元素存在target，返回最后一个等于target的元素下标，否则返回第一个大于target的元素下标
int floor_upper(vector<int>& arr, int target)
{
int l = 0;
int r = arr.size() - 1;
if (arr[r] < target)
{
return -1;
}
int res = -1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (arr[mid] > target)
{
res = mid;
r = mid - 1;
}
else if (arr[mid] == target)
{
//找到target时，收缩左边界找最后一个
res = mid;
l = mid + 1;
}
else
{
l = mid + 1;
}
}
//检查res位置是否为target
if (res < arr.size() && arr[res] == target)
{
while (res + 1 < arr.size() && arr[res + 1] == target)
{
res++;
}
return res;
}
return res;
}
//寻找最后一个小于target的下标
int lower(vector<int>& arr, int target)
{
int l = 0;
int r = arr.size() - 1;
int res = -1;
while (l <= r)
{
int mid = l + (r-l)/2;
if (arr[mid] < target)
{
res = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return res;
}
//返回第一个等于target的下标
int floor_lower(vector<int>& arr, int target)
{
int l = 0;
int r = arr.size() - 1;
int res = -1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (arr[mid] >= target)
{
if (arr[mid] == target)
{
res = mid;
}
r = mid - 1;//继续向左寻找更小的
}
else
{
res = mid;//记录最后一个小于target的位置
l = mid + 1;
}
}
if (res != -1 && arr[res] == target)
{
while (res > 0 && arr[res - 1] == target)
{
res--;
}
return res;
}
return res;
}