1、二分查找法
我们这次实现一个比线性查找法快很多的算法，二分查找法，它的复杂度是 O(logN)
public class BinarySearch {
private BinarySearch() {
}
/**
* 二分查找法递归实现
*/
public static <E extends Comparable<E>> int searchR(E[] data, E target) {
return searchR(data, 0, data.length - 1, target);
}
private static <E extends Comparable<E>> int searchR(E[] data, int l, int r, E target) {
if (l > r) return -1;
int mid = l + (r - l) / 2;
if (data[mid].compareTo(target) == 0) return mid;
if (data[mid].compareTo(target) < 0) return searchR(data, mid + 1, r, target);
return searchR(data, l, mid - 1, target);
}
/**
* 二分查找法非递归实现
*/
public static <E extends Comparable<E>> int search(E[] data, E target) {
int l = 0;
int r = data.length - 1;
int mid;
// 在 data[l, r] 中查找 target
// 每次循环开始时: data[l]、data[r] 还没看, 因此 l == r 时, 依然要进入循环
while (l <= r) {
mid = l + (r - l) / 2;
if (data[mid].compareTo(target) == 0) return mid;
if (data[mid].compareTo(target) < 0) l = mid + 1;
else r = mid - 1;
}
return -1;
}
}
2、Ceil 上界
public class Ceil {
private Ceil() {
}
/**
* 在 data[] 中查找 > target 的最小值所在的索引
*/
private static <E extends Comparable<E>> int upper(E[] data, E target) {
int l = 0;
int r = data.length;
int mid;
// 在 data[l, r] 中查找 > target 的最左边的索引, r = data.length
// 每次循环开始时: data[l] 还没看, data[r] 可能是解, 因此当 l == r 时, r 就是解
while (l < r) {
mid = l + (r - l) / 2; // l <= mid < r, l 与 r 相邻时 mid = l
if (data[mid].compareTo(target) > 0) r = mid;
else l = mid + 1;
}
return r;
}
/**
* <p>存在 target 时, 返回 = target 的最右边的索引
* <p>没有 target 时, 返回 > target 的最左边的索引
*/
public static <E extends Comparable<E>> int ceilR(E[] data, E target) {
int upper = upper(data, target);
if (upper - 1 >= 0 && data[upper - 1].compareTo(target) == 0) return upper - 1;
return upper;
}
/**
* <p>存在 target 时, 返回 = target 的最左边的索引
* <p>没有 target 时, 返回 > target 的最左边的索引
*/
public static <E extends Comparable<E>> int ceilL(E[] data, E target) {
int l = 0;
int r = data.length;
int mid;
// 在 data[l, r] 中查找 >= target 的最左边的索引, r = data.length
// 每次循环开始时: data[l] 还没看, data[r] 可能是解, 因此当 l == r 时, r 就是解
while (l < r) {
mid = l + (r - l) / 2; // l <= mid < r, l 与 r 相邻时 mid = l
if (data[mid].compareTo(target) >= 0) r = mid;
else l = mid + 1;
}
return r;
}
}
3、Floor 下界
public class Ceil {
private Ceil() {
}
/**
* 在 data[] 中查找 > target 的最小值所在的索引
*/
private static <E extends Comparable<E>> int upper(E[] data, E target) {
int l = 0;
int r = data.length;
int mid;
// 在 data[l, r] 中查找 > target 的最左边的索引, r = data.length
// 每次循环开始时: data[l] 还没看, data[r] 可能是解, 因此当 l == r 时, r 就是解
while (l < r) {
mid = l + (r - l) / 2; // l <= mid < r, l 与 r 相邻时 mid = l
if (data[mid].compareTo(target) > 0) r = mid;
else l = mid + 1;
}
return r;
}
/**
* <p>存在 target 时, 返回 = target 的最右边的索引
* <p>没有 target 时, 返回 > target 的最左边的索引
*/
public static <E extends Comparable<E>> int ceilR(E[] data, E target) {
int upper = upper(data, target);
if (upper - 1 >= 0 && data[upper - 1].compareTo(target) == 0) return upper - 1;
return upper;
}
/**
* <p>存在 target 时, 返回 = target 的最左边的索引
* <p>没有 target 时, 返回 > target 的最左边的索引
*/
public static <E extends Comparable<E>> int ceilL(E[] data, E target) {
int l = 0;
int r = data.length;
int mid;
// 在 data[l, r] 中查找 >= target 的最左边的索引, r = data.length
// 每次循环开始时: data[l] 还没看, data[r] 可能是解, 因此当 l == r 时, r 就是解
while (l < r) {
mid = l + (r - l) / 2; // l <= mid < r, l 与 r 相邻时 mid = l
if (data[mid].compareTo(target) >= 0) r = mid;
else l = mid + 1;
}
return r;
}
}