二分查找详解

LeetCode	力扣	难度
34. Find First and Last Position of Element in Sorted Array	34. 在排序数组中查找元素的第一个和最后一个位置	🟠
704. Binary Search	704. 二分查找	🟢
-	剑指 Offer 53 - I. 在排序数组中查找数字 I	🟢

-----------

一、寻找一个数(相同的取最左边) §

/**  
 * 二分搜索，并找最左边的元素  
 *  
 * @param a  
 * @param n  
 * @param value  
 * @return  
 */  
public int bsearch_LeftMost(int[] a, int n, int value) {  
    int low = 0;  
    int high = n - 1;  
    while (low <= high) {  
        int mid = low + ((high - low) >> 1);  
        if (a[mid] > value) {  
            high = mid - 1;  
        } else if (a[mid] < value) {  
            low = mid + 1;  
        } else {  
            if ((mid == 0) || (a[mid - 1] != value)) return mid; // 最左逼近  
            else high = mid - 1;  
        }  
    }  
    return -1;  
}

二、寻找一个数(相同的取最右边) §

/**  
 * 二分搜索最右边的元素  
 *  
 * @param a  
 * @param n  
 * @param value  
 * @return  
 */  
public int bsearch_RightMost(int[] a, int n, int value) {  
    int low = 0;  
    int high = n - 1;  
    while (low <= high) {  
        int mid = low + ((high - low) >> 1);  
        if (a[mid] > value) {  
            high = mid - 1;  
        } else if (a[mid] < value) {  
            low = mid + 1;  
        } else {  
            if ((mid == n - 1) || (a[mid + 1] != value)) return mid; // 往右边逼近  
            else low = mid + 1;  
        }  
    }  
    return -1;  
}

三、寻找第一个大于等于的数 §

/**  
 * 第一个大于等于元素  
 *  
 * @param a  
 * @param n  
 * @param value  
 * @return  
 */  
public int bsearch_GE(int[] a, int n, int value) {  
    int low = 0;  
    int high = n - 1;  
    while (low <= high) {  
        int mid = low + ((high - low) >> 1);  
        if (a[mid] >= value) {  
            if ((mid == 0) || (a[mid - 1] < value)) return mid;  
            else high = mid - 1;  
        } else {  
            low = mid + 1;  
        }  
    }  
    return -1;  
}

四、寻找最后一个小于等于的数 §

/**  
 * 最后一个小于等于  
 *  
 * @param a  
 * @param n  
 * @param value  
 * @return  
 */  
public int bsearch_LE(int[] a, int n, int value) {  
    int low = 0;  
    int high = n - 1;  
    while (low <= high) {  
        int mid = low + ((high - low) >> 1);  
        if (a[mid] > value) {  
            high = mid - 1;  
        } else {  
            if ((mid == n - 1) || (a[mid + 1] > value)) return mid;  
            else low = mid + 1;  
        }  
    }
      
    return -1;  
}