二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组已经为空,则表示找不到指定的元素。这种搜索算法每一次比较都使搜索范围缩小一半,其时间复杂度是O(logN)。
package com.query.half.utils;
import java.util.Comparator;
/**
* 二分查找 工具类
* @author huang
*
*/
public class HalfQueryUtil {
private HalfQueryUtil() {
super();
}
public static <T> int binarySearch(T[] list, T key, Comparator<T> comparator) {
if(null == list || null == comparator) {
return -1;
}
int retIndex = -1;
int start = 0;
int end = list.length;
int middle = 0;
int compareResult = 0;
while(start < (end-1)) {
middle = (start + end) >>> 1;
compareResult = comparator.compare(list[middle], key);
if(compareResult > 0) {
// start = start;
end = middle;
} else if(compareResult < 0) {
start = middle;
// end = end;
} else {
retIndex = middle;
break;
}
}
return retIndex;
}
public static <T extends Comparable<T>> int binarySearch(T[] list, T key, int start, int end) {
if(start <= end) {
int middle = (start + end) >>> 1;
int compareResult = key.compareTo(list[middle]);
if(compareResult > 0) {
start = middle + 1;
// end = end;
return binarySearch(list, key, start, end-1);
} else if(compareResult < 0) {
// start = start;
end = middle - 1;
return binarySearch(list, key, start, end-1);
} else {
return middle;
}
}
return -1;
}
}
注:需要注意的是计算中间位置时不应该使用(high+ low) / 2的方式,因为加法运算可能导致整数越界,这里应该使用以下三种方式之一:
end + (start – end) / 2
或
end + (start – end) >> 1
或
(end + start) >>> 1