关于二分法边界的一点思考

关于二分法边界的一点思考

边界误用

对于二分搜索区间有两种形式,一种是左闭右开,一种是左闭右闭,区别在于初始右边界的赋值,如果是:right = arr.length 显然是左闭右开,而right=arr.length-1则为左闭右闭,两种区间选择不同导致后续缩小搜索区间也有不同的形式。

需要注意的是, 循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则

int search1(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n - 1;

    while (left <= right)
    {
        middle = (left + right) / 2;
        if (array[middle] > v)
        {
            right = middle - 1; //[left,mid-1]保持区间一致
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}

int search2(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n;

    while (left < right) //没有等号
    {
        middle = (left + right) / 2;

        if (array[middle] > v)
        {
            right = middle; //区间[left,mid)保持一致
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}

左右边界

二分查找在面对有序数组时,能够极大减少搜索次数,对于二分查找典型的应用有:

  • 目标值查找:这种应用最为典型,只需要遵守基本的二分查找步骤就行,不再详细说明
  • 目标位置查找:

关于二分法边界的一点思考

  • 对于本题,需要查找到的是citations[i] >= lenght-i的有区间长度
  • 开始的误用:在这里我所思考的是,最后区间会收缩在目标边界的右边,在最后一次判断后左边界+1正好为目标边界值,而出错就在于求得不是边界索引,而是此时右区间长度。
public int hIndex(int[] citations) {
    int l = 0;
    int r = citations.length - 1;
    while (r >= l) {
        int m = l + r >> 1;
        if (citations[m] == citations.length - m) {
            return citations[m];
        } else if (citations[m] > citations.length - m){
            r = m - 1;
        }
        else
            l=m+1;
    }
    return l;
}

一点反思:需要注意边界情况,如为空、为1

  • 修正:
public int hIndex(int[] citations) {
    int l = 0;
    int r = citations.length - 1;
    while (r >= l) {
        int m = l + r >> 1;
        if (citations[m] == citations.length - m) {
            return citations[m];
        } else if (citations[m] > citations.length - m) {
            r = m - 1;
        } else
            l = m + 1;
    }
    return citations.length - l;
}

总结

  • 不要过分关注区间收拢细节,需要关注最后边界收拢情况
  • 注意所求目标
  • 注意边界情况
上一篇:习题6-3 使用函数输出指定范围内的完数 (20 分)


下一篇:通过stylish调整SF首页样式来增加识别度