基本算法篇——二分查找
二分查找简述
二分查找模板
二分查找边界
例题数的范围
二分查找简述
首先我们来简单介绍一下二分查找：
二分查找通常是在有单调性的数组中进行；有单调性的数组必定可以二分，但二分可以运行在没有单调数的数组中
确定一个分界点
// 同样我们需要先确定一个分界点
// 我们的二分查找的分界点通常设计为(l+r/2或者(l+r+1/2，至于为什么+1我们后面讲解确定一个查找条件
// 我们需要给出一个你查找数所满足的条件
// 我们需要确定数组的一侧不满足这个条件，但另一侧满足这个条件
// 这时我们就只需要查找这个我们需要的数，使其一侧不满足条件，而另一侧满足条件更换边界值，不断进行递归查找
// 我们采用一种check算法来检查mid值是否满足条件，然后根据是否满足条件来判断我们所需要查找的值在哪一侧
// 然后我们更换边界值，不断进行运算，直到l==r时，这时会锁定一个数，而这个数就是我们所需要的数二分查找模板
我们在实际使用中的二分查找模板只有两套，我们在下面给出：
第一套模板
int bsearch_1(int l,int r{
// 区间[l,r]划分为[l,mid]和[mid+1,r]使用
// 首先对整个数组进行遍历
while(l < r{
// 约定一个起始的分界点
int mid = (l+r/2;
// 对该分界点进行判定
if(check(mid{
// 如果满足条件时该点在[l,mid]之间
r = mid;
} else {
// 如果不满足条件时该点在[mid+1,r]之间
l = mid + 1;
}
}
// 最后我们l==r，这个点就是我们二分查找出来的点
return l;
}第二套模板
int bsearch_1(int l,int r{
// 区间[l,r]划分为[l,mid - 1]和[mid,r]使用
// 首先对整个数组进行遍历
while(l < r{
// 约定一个起始的分界点
int mid = (l+r+1/2;
// 对该分界点进行判定
if(check(mid{
// 如果满足条件时该点在[mid,r]之间
l = mid;
} else {
// 如果不满足条件，说明该点在[l,mid - 1]之间
r = mid - 1;
}
}
// 最后我们l==r，这个点就是我们二分查找出来的点
return l;
}二分查找边界
我们现在来介绍一下二分查找边界问题，也就是为什么+1：
int bsearch_1(int l,int r{
// 区间[l,r]划分为[l,mid - 1]和[mid,r]使用
// 首先对整个数组进行遍历
while(l < r{
// 约定一个起始的分界点
int mid = (l+r+1/2;
// 对该分界点进行判定
if(check(mid{
// 如果满足条件时该点在[mid,r]之间
l = mid;
} else {
// 如果不满足条件，说明该点在[l,mid - 1]之间
r = mid - 1;
}
}
// 最后我们l==r，这个点就是我们二分查找出来的点
return l;
}
/*
上述是+1的模板，我们+1的根本原因是因为边界问题，
因为我们将边界设置为l=mid，所以我们才需要对mid的赋值进行+1操作
因为我们的int类型是向下整分的，也就是2.5会变为2
那么如果我们的l = r - 1，这种情况下，我们的将l = mid = （l + l + 1）/2，这时l不会发生变化，我们的范围还是[l,r]不改变
因此为了避免无限循环，所以我们需要将mid的值加上0.5(1，这时我们再将l = mid，l就会向前进1，这时就不会发生循环
*/例题数的范围
例题：
我们给定一个数组，按顺序排列，我们需要得知其中某些数的起始位置和终止位置，若无该数返回-1 -1；
import java.util.Scanner;
public class Postion {
public static void main(String[] args {
// 输入框
Scanner scanner = new Scanner(System.in;
// 数组长度
int n = scanner.nextInt(;
// 查找个数
int k = scanner.nextInt(;
// 数组内容
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++ {
arr[i] = scanner.nextInt(;
}
// 开始循环
while (k-- > 0{
// 设置查找值
int x = scanner.nextInt(;
// 边界设置
int l = 0,r = n-1;
// 开始二分查找
while (l < r{
// 先找左边界
int mid = (l+r/2;
if (arr[mid] >= x{
r = mid;
}else {
l = mid + 1;
}
}
// 判定是否有这个数
if (arr[l] != x{
// 如果没有k返回return
System.out.println("-1,-1";
}else {
// 如果有k，先打印左边界，我们再找右边界；(注意：此时r=l
System.out.println(l + " ";
l = 0;
r = n-1;
while (l < r{
// 查找右边界
int mid = (l+r+1/2;
if (arr[mid] <= x{
l = mid;
}else {
r = mid - 1;
}
}
}
// 打印右边界(注意：此时r=l
System.out.println(l;
}
}
}结束语
好的，关于基础算法篇的二分查找就介绍到这里，希望能为你带来帮助~