二分查找 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

求最近邻居

  • 前任和后任距离更近者
最后修改:2023 年 03 月 08 日
如果觉得我的文章对你有用,请随意赞赏