二分查找（binary search）是非常基礎(chǔ)的算法短纵，日常應(yīng)用和面試中都極常見。其思想簡單僵控，不再贅述香到，但想要寫好二分查找，也并不是那么容易的报破。
圖來自《算法（第4版）》
- 經(jīng)典算法（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;
}
- 如有多個(gè)等于target的值，查找第一個(gè)相等的值充易，否則返回-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;
}
為什么不仍然使用經(jīng)典算法梗脾，最后加一個(gè)for循環(huán)來找到符合條件的元素呢？
如果序列很長盹靴，且相等值有很多重復(fù)的話炸茧，算法效率有可能會(huì)因此由O(logn)退化為O(n)帆疟。
- 如有多個(gè)等于target的值，查找第一個(gè)相等的值宇立，否則查找第一個(gè)大于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;
}
- 查找第一個(gè)大于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;
}
同樣地，既然可以查找“第一個(gè)”自赔，那么就可以查找“最后一個(gè)”妈嘹。
- 如有多個(gè)等于target的值，查找最后一個(gè)相等的值绍妨，否則返回-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;
}
- 如有多個(gè)等于target的值润脸，查找最后一個(gè)相等的值，否則查找最后一個(gè)小于target的值
- 查找最后一個(gè)小于target的值
參考上面的思路他去，相信這兩個(gè)也就不難做了毙驯。
總之，弄清楚array[mid]與target之間的大小關(guān)系灾测，以及最終需要返回low/mid/high三者之間的哪一個(gè)值爆价，問題就可迎刃而解。
