二分查找 leftRightmost

当数组中出现重复元素时，原本的二分查找方法并不能准确找出目标值第一次出现的位置，这时候就需要改进的方法来完成需求

二分查找leftmost

代码：

Params: a - 待查找的升序数组

​ target - 待查找的目标值

Returns:

​ 找到则返回最靠左索引

​ 找不到返回-1

public static int binarySearchLeftmost1(int[] a, int target){
    int i = 0, j = a.lengh -1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]){
            j  = m  - 1;
        } else if(a[m] < target) {
            i = m + 1;
        } else {
            // 记录候选位置
            candidate = m;
            j = m -1;
        }
    }
    return candidate;
}

二分查找rightmost

代码：

Params: a - 待查找的升序数组

​ target - 待查找的目标值

Returns:

​ 找到则返回最靠右索引

​ 找不到返回-1

public static int binarySearchLeftmost1(int[] a, int target){
    int i = 0, j = a.lengh -1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]){
            j  = m  - 1;
        } else if(a[m] < target) {
            i = m + 1;
        } else {
            // 记录候选位置
            candidate = m;
            i = m + 1;
        }
    }
    return candidate;
}

二分查找leftmost改

代码：

Params: a - 待查找的升序数组

​ target - 待查找的目标值

Returns:

​ 返回>= target的最靠左索引

public static int binarySearchLeftmost2(int[] a, int target){
    int i = 0, j = a.lengh -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target <= a[m]){
            j  = m  - 1;
        } else {
            i = m + 1;
        } 
    }
    return i - 1;
}

二分查找rightmost改

代码：

Params: a - 待查找的升序数组

​ target - 待查找的目标值

Returns:

​ 返回<= target的最靠右索引

public static int binarySearchLeftmost2(int[] a, int target){
    int i = 0, j = a.lengh -1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]){
            j  = m  - 1;
        } else {
            i = m + 1;
        } 
    }
    return i - 1;
}

范围查询：

• 查询 x< 4，0 .. leftmost(4) - 1
• 查询 x > 4，0 .. rightmost(4)
• 查询 4 < x，rightmost(4) + 1 .. 无穷大
• 查询 4 > x， leftmost(4) .. 无穷大
• 查询 4 > x > 7，leftmost(4) .. rightmost(7)
• 查询 4 < x < 7，rightmost(4)+1 .. leftmost(7)-1

求排名：leftmost(target) + 1

• target 可以不存在，如：leftmost(5)+1 = 6
• target 也可以存在，如：leftmost(4)+1 = 3

求前任（predecessor）：leftmost(target) - 1

• leftmost(3) - 1 = 1，前任 a_1 = 2
• leftmost(4) - 1 = 1，前任 a_1 = 2

求后任（successor）：rightmost(target)+1

• rightmost(5) + 1 = 5，后任 a_5 = 7
• rightmost(4) + 1 = 5，后任 a_5 = 7

求最近邻居：

• 前任和后任距离更近者