如果数据存储是有序的，那么我们可以考虑使用二分查找，查询我们需要的数据，这种查找比线性查找快很多，尤其对大数组来说更为明显。二分查找也叫折半查找。
借图来源：http://www.penjee.com
可以看出使用二分查找在查找数字 37 时只需3次，而线性查找查找37时需要11次。线性查找最坏的情况需要遍历整个数据。
二分查找步骤如下：
| 步数 | 所猜的数 | 结果 | 可能值的范围 |
|---|---|---|---|
| 0 | 1~59 | ||
| 1 | 23 | 太低 | 29~59 |
| 2 | 41 | 太高 | 29~37 |
| 3 | 31 | 太低 | 37~37 |
| 4 | 37 | 正确 |
一、二分查找代码实现
/**
* @Author: zhuzhaolin
* @Date: 2021/05/03/21:41
* @Description:
*/
public class BinarySearch {
private final int arraySize;
private int[] orderArrays;
public BinarySearch(int[] orderArrays) {
this.arraySize = orderArrays.length;
this.orderArrays = orderArrays;
}
public static void main(String[] args) {
int[] orderArrays = {1, 3, 5 ,7 , 11 ,13 ,17 , 19 , 23 ,29 , 31 , 37 , 41 , 43 , 47 , 53 , 59};
BinarySearch binarySearch = new BinarySearch(orderArrays);
System.out.println(binarySearch.find(37).get());
System.out.println(binarySearch.find(100).isPresent());
}
private Optional<Integer> find(long searchKey) {
int lowerBound = 0;
int upperBound = arraySize - 1;
int mid;
while (true) {
mid = (lowerBound + upperBound) / 2;
System.out.println("当前找到的值：" +orderArrays[mid]);
if (orderArrays[mid] == searchKey) {
return Optional.of(mid);
} else if (lowerBound > upperBound) {
System.out.println("没有找到值");
return Optional.empty();
} else {
//如果searchKey较大，则应该将范围设为当前范围的后半部。因此lowerBund移到mid。实际上是将lowerBound移到mid后一个数据项。
if (orderArrays[mid] < searchKey) {
//在上半部
lowerBound = mid + 1;
} else {
//如果search比mid[mid]小，则将范围设为当前范围的前半部。因此将upperBound移到mid的前一个数据项。
//在下半部
upperBound = mid - 1;
}
}
}
}
}
执行结果
当前找到的值：23
当前找到的值：41
当前找到的值：31
当前找到的值：37
11
核心find方法一开始设变量lowerBound 和upperBound指向数组的第一个和最后一个非空数据项。通过设置这些变量可以确定查找searchKey数据项的范围。然后在while循环中，当前的下标mid被设置为这个范围的中间值。
如果足够幸运的话，mid可能直接返回就是指向所需要的数据项，所以先查看是否相等。如果是，则意味找到了需要的数据项，下一步返回它的下标mid。
循环中的每一步将范围缩小一半。最终这个范围会小到无法再分割。在下一个语句中会判断：如果lowerBound 比upperBound大，则范围已经不在了，停止查找并返回空。
如果mid没有指向所需要的数据项，但范围仍足够大，此时需要将范围缩小一半。比较当前下标所指的orderArrays[mid]，即范围中部值与待查数据的值searchKey。
- 如果
searchKey较大，则应该将范围设为当前范围的后半部。因此lowerBund移到mid。实际上是将lowerBound移到mid后一个数据项。 - 如果
searchKey比mid[mid]小，则将范围设为当前范围的前半部。因此将upperBound移到mid`的前一个数据项。
二分查找中的范围分割
二、递归取代循环
在递归的方法中，不用改变lowerBound或者upperBound，而是用lowerBound或者upperBound的新值作为参数反复调用find()方法。
private Optional<Integer> find1(long searchKey) {
return recFind(searchKey , 0 , orderArrays.length-1);
}
private Optional<Integer> recFind(long searchKey , int lowerBound ,int upperBound ){
int curIn;
curIn = (lowerBound + upperBound)/2;
if (orderArrays[curIn] == searchKey){
return Optional.of(curIn);
}else if (lowerBound > upperBound){
System.out.println("没有找到值");
return Optional.empty();
}else {
if (orderArrays[curIn] <searchKey){
return recFind(searchKey , curIn+1 ,upperBound);
}else {
return recFind(searchKey , lowerBound , curIn-1);
}
}
}
