二分算法笔记

三个模板

基础模板

这个板子是最基础的折半查找,既不偏左也不偏右

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

acwing的算法板子

模板一

当我们将区间[l, r]划分成[l, mid][mid + 1, r]时,其更新操作是r = mid或者l = mid + 1;,计算mid时不需要加1。

int bsearch_1(int l, int r) // 这个模板实质从左往右找
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

模板二

当我们将区间[l, r]划分成[l, mid - 1][mid, r]时,其更新操作是r = mid - 1或者l = mid;,此时为了防止死循环,计算mid时需要加1。

int bsearch_2(int l, int r) // 这个模板实质从右往左找
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

使用板子的时候要注意数据范围,计算mid时可能会爆int,因此推荐默认使用long long来声明mid

【深基13.例1】查找

模板题

因为要输出的是数字第一次出现的位置且数字可能出现多次,因此使用模板一

check条件为a[mid] <= target,若要找的是数字最后出现的位置,则使用模板二,check条件为a[mid] >= target

上一篇:shell获取函数返回值


下一篇:IP协议TTL