二分查找（binary search）是非常基础的算法，日常应用和面试中都极常见。其思想简单，不再赘述，但想要写好二分查找，也并不是那么容易的。
图来自《算法（第4版）》
- 经典算法（array是升序序列，下同）
int binarySearch(int target, int[] array) {
int low = 0, high = array.length - 1;
// 注意<=
while (low <= high) {
// 防止low + high溢出
int mid = low + (high - low) / 2;
if (array[mid] < target) {
low = mid + 1;
} else if (array[mid] > target) {
high = mid - 1;
} else { // =
return mid;
}
}
return -1;
}
- 如有多个等于target的值，查找第一个相等的值，否则返回-1
int binarySearchFirstEq(int target, int[] array) {
int low = 0, high = array.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] < target) {
low = mid + 1;
} else { // >=
high = mid - 1;
}
}
if (array[low] == target) {
return low;
}
return -1;
}
为什么不仍然使用经典算法，最后加一个for循环来找到符合条件的元素呢？
如果序列很长，且相等值有很多重复的话，算法效率有可能会因此由O(logn)退化为O(n)。
- 如有多个等于target的值，查找第一个相等的值，否则查找第一个大于target的值
int binarySearchFirstGte(int target, int[] array) {
int low = 0, high = array.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] < target) {
low = mid + 1;
} else { // >=
high = mid - 1;
}
}
return low;
}
- 查找第一个大于target的值
int binarySearchFirstGt(int target, int[] array) {
int low = 0, high = array.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] <= target) {
low = mid + 1;
} else { // >
high = mid - 1;
}
}
return low;
}
同样地，既然可以查找“第一个”，那么就可以查找“最后一个”。
- 如有多个等于target的值，查找最后一个相等的值，否则返回-1
int binarySearchLastEq(int target, int[] array) {
int low = 0, high = array.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] <= target) {
low = mid + 1;
} else { // >
high = mid - 1;
}
}
if (array[high] == target) {
return high;
}
return -1;
}
- 如有多个等于target的值，查找最后一个相等的值，否则查找最后一个小于target的值
- 查找最后一个小于target的值
参考上面的思路，相信这两个也就不难做了。
总之，弄清楚array[mid]与target之间的大小关系，以及最终需要返回low/mid/high三者之间的哪一个值，问题就可迎刃而解。
