二分查找變種

該算法有很多版本，這裡給出java中實作比較好的一種方式。其中，

>>>

為無符号右移。

二分查找第一個值為obj的元素

/**
 * 二分查找第一個值為obj的元素
 * @param array
 * @param obj
 * @return 若數組為空，傳回-1; 若查找到，則傳回其索引; 若未查找到，傳回負值（可能為-1）
 */
public static int binarySearchFirstEqual (int[] array, int obj) {
    if (array == null || array.length == 0) {
        return -1;
    }
    int left = 0;
    int right = array.length - 1;
    while (left < right) {
        int mid = left + ((right - left) >>> 1);
        if (array[mid] < obj) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    if (array[left] == obj) {
        return left;
    }
    return -(left + 1);    // 參照官方文檔自定義值
}
           

二分查找最後一個值為obj的元素

/**
 * 二分查找最後一個值為obj的元素
 * @param array
 * @param obj
 * @return 若數組為空，傳回-1; 若查找到，則傳回其索引; 若未查找到，傳回負值（可能為-1）
 */
public static int binarySearchLastEqual (int[] array, int obj) {
    if (array == null || array.length == 0) {
        return -1;
    }
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >>> 1);
        if (array[mid] <= obj) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (right >= 0 && array[right] == obj) {
        return right;
    }
    return -(right + 1);    // 參照官方文檔自定義值
}
           

比較好的文章

你真的會寫二分查找嗎

『注:本文來自部落格園“小溪的部落格”，若非聲明均為原創内容，請勿用于商業用途，轉載請注明出處http://www.cnblogs.com/xiaoxi666/』