原理
1.查找数组的中间索引,比较中间索引处元素与查找元素是否相等
2.若中间索引处元素比查找元素大,则去索引范围为【开始索引,中间索引-1】的区域内继续从第一步开始查找
3.若中间索引处元素比查找元素小,则去索引范围为【中间索引+1,结束索引】的区域内继续从第一步开始查找
4.若中间索引处元素与查找元素相等,校验索引为【中间索引-1】的元素是否与查找相等
5.若不相等,则返回中间索引
6.若相等,则去索引范围为【开始索引,中间索引-1】的区域内继续从第一步开始查找(这是因为相同元素可能有多个,需要查找到第一个)
示例
package wxw.mengyuan;
import java.util.Comparator;
import java.util.List;
public class BinarySearch {
/**
* 堆代码 duidaima.com
* 在已排序好的集合中查找值所在的第一个索引
* @param source 排序好的集合
* @param value 要匹配的值
* @param comparator 比较器
* @return 查找到的第一个索引
*/
static <T extends Comparable<T>> int search(List<T> source, T value, Comparator<T> comparator) {
return search(source, 0, source.size() - 1, value, comparator);
}
/**
* 在指定范围内进行查找
* @param source 排序好的集合
* @param begin 范围的开始
* @param end 范围的结束
* @param value 要匹配的值
* @param comparator 比较器
* @return 查找到的第一个索引
*/
private static <T extends Comparable<T>> int search(List<T> source, int begin, int end, T value, Comparator<T> comparator) {
// 没有查询到,返回索引-1
if (begin > end) {
return -1;
}
// 计算中间索引
int middle = (begin + end) / 2;
// 计算匹配值与中间值的大小
int compare = comparator.compare(value, source.get(middle));
if (compare == 0) {
// 若中间值与要匹配的值相等
if (value.compareTo(source.get(middle - 1)) == 0) {
// 若中间值的前一个元素与匹配值也相等,表示前面还有可匹配上的元素,继续去查找第一次匹配的索引
return search(source, begin, middle - 1, value, comparator);
} else {
// 返回当前中间值的索引
return middle;
}
} else if (compare < 0) {
// 若匹配的值比中间小
return search(source, begin, middle - 1, value, comparator);
} else {
// 若匹配的值比中间大
return search(source, middle + 1, end, value, comparator);
}
}
}