資料結構與演算法——二分查詢練習
1. 概述
前面說到了二分查詢問題，看起來非常的簡單，的確，前面的兩種實現都不難，程式碼也很容易寫，因為那只是最基礎的二分查詢問題了。今天來看看幾種稍微複雜的二分查詢問題：
- 查詢第一個等於給定值的元素
- 查詢最後一個等於給定值的元素
- 查詢第一個大於等於給定值的元素
- 查詢最後一個小於等於給定值的元素
1. 查詢第一個等於給定值的元素
假如有一個數組 data[1,3,5,5,5,7,8,10,12] ，我們要查詢第一個等於 5 的值，該怎麼實現呢？如果按照普通的二分查詢演算法，取中間 data[4]=5，剛好等於要查詢的值 5，所以程式就返回下標 4。但是很明顯不正確，因為我們要找的是第一個 5，下標為 2，那應該怎麼實現呢？先來看看程式碼吧：
public static int findFirst(int[] data, int value) {
int low = 0;
int high = data.length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (data[mid] == value) {
if (mid == 0 || data[mid - 1] != value) return mid;
else high = mid - 1;
}
else if (data[mid] < value) low = mid + 1;
else high = mid - 1;
}
return -1;
}
這裡的程式碼和前面的普通二分查詢很類似，只是在判斷 data[mid] == value 的時候，會有一些不一樣，如果 mid 等於 0，則表示這是陣列的第一個元素，那麼肯定就是我們要找的元素，第二種情況，如果 mid 的前一位不等於 value，那麼也是我們要找的元素。
3. 查詢最後一個等於給定值的元素
這種變形的二分查詢和上面的這種情況很類似，還是利用上面的那個陣列 data[1,3,4,5,5,5,5,10,12]，我們要查詢最後一個等於 5 的元素。實現的程式碼也和上面的類似：
public static int findLast(int[] data, int value) {
int low = 0;
int high = data.length - 1;
while (low <= high) {
int mid = low + ((high - low));
if (data[mid] == value) {
if (mid == data.length - 1 || data[mid + 1] != value) return mid;
else low = mid + 1;
}
else if (data[mid] < value) low = mid + 1;
else high = mid - 1;
}
return -1;
}
在 data[mid] == value 的時候，會進行判斷，如果 mid 等於陣列 length - 1，則說明是陣列的最後一個元素，那麼肯定是我們查詢的，如果 mid 的前面一個元素不等於 value，則說明也是我們要查詢的。邏輯跟上面說到的查詢第一個等於給定值的情況相反。
4. 查詢第一個大於等於給定值的元素
例如一個數組 data[1,3,5,5,5,8,8,8,10,12]，我們要查詢第一個大於等於 7 的值，就是下標為 5 的值 8，應該怎麼做呢？實際上實現的思路和上面的兩種問題類似，程式碼其實還更簡潔：
public static int findFirstBigger(int[] data, int value) {
int low = 0;
int high = data.length - 1;
while (low <= high){
int mid = low + ((high - low) >> 1);
if (data[mid] >= value){
if (mid == 0 || data[mid - 1] < value) return mid;
else high = mid - 1;
}
else low = mid + 1;
}
return -1;
}
當 data[mid] >= value 的時候，進行統一處理，這裡有兩個判斷，一是如果 mid 等於 0，表示 mid 是陣列的第一個元素，那麼肯定就是我們要找的元素，第二種情況是，如果 mid 的前一個元素小於 value，那麼也是我們要查詢的元素。
5. 查詢最後一個小於等於給定值的元素
有了對前面三種情況的理解，其實再來寫這種情況的程式碼就很簡單了，直接給出程式碼：
public static int findLastSmaller(int[] data, int value) {
int low = 0;
int high = data.length - 1;
while (low <= high){
int mid = low + ((high - low) >> 1);
if (data[mid] <= value){
if (mid == data.length - 1 || data[mid + 1] > value) return mid;
else low = mid + 1;
}
else high = mid - 1;
}
return -1;
}
當然，這只是眾多二分查詢變形問題中常見的幾種，可以多理解一下，自己動手實現一下。也可以拓展一些思維，例如上面的查詢小於等於或者大於等於的情況，如果只是查詢小於或者大於，該怎麼實現呢，只需要將程式碼的一些細節稍作修改即可。