二分查找的mid值确定以及check函数的确定

小林嘞

已于 2023-03-12 14:47:20 修改

阅读量1.7k

点赞数 5

分类专栏：力扣刷题文章标签：数据结构

于 2023-03-08 09:37:11 首次发布

本文链接： https://blog.csdn.net/weixin_41636858/article/details/129396546

版权

力扣刷题专栏收录该内容

40 篇文章 3 订阅

订阅专栏

文章讨论了如何使用二分查找法确定mid值来高效地在排序数组中找到目标值的第一个和最后一个位置。两种mid值的确定方式会影响到check函数的处理以及区间划分，强调了在不满足条件时如何调整左右边界以复现区间。最后给出了力扣题目的例子，展示了在O(logn)时间复杂度内解决此类问题的算法实现。

摘要由CSDN通过智能技术生成

1.mid值确定

mid值的确定分为以下两种：

int mid = left + right >> 1;

int mid = left + right + 1 >> 1;

这两种写法的区别是：第一种将区间分成 [0, mid] [mid+1, n]

第二种将区间分成[0,mid - 1] [mid, n]

那么根据需要，我们就要判断check函数的写法了：

2.check函数

check函数的确定如上图所示，具体可以记忆为所找的范围为 target前面的符号的指向。

如果是 <= 则找的是全部 <= 目标的数值，反之亦然。

确定了check函数之后，我们要确定二次取区间的问题，这个问题需要结合前面的mid值划分来解决

//对于 mid = left + right >> 1
//因为划分为了[0, mid] [mid + 1, n]，
//所以不满足check后，要取left = mid + 1 ,right = mid
//也就是说，要复现区间。

//对于 mid = left + right >> 1
//因为划分为了[0, mid] [mid + 1, n]，
//所以不满足check后，要取left = mid + 1 ,right = mid 
//也就是说，要复现区间。
while( left < right)
{
    int mid = (right + left)/2 + left;
    if( check(mid) )
    {
        left = mid + 1;
    }
    else
    {
        right = mid;
    }
}

同理对于另一种mid取值的方法：

一样都是去复现划分后的情况[0,mid - 1] [mid , n]

while( left < right)
{
    int mid = (right + left + 1) /2 + left;
    if( check(mid))
    {
        right = mid -1;
    }
    else
    {
        left = mid;
    }
}

另外也可以这样理解：

当 check（mid） == true 调整的是 l 时：计算 mid 的方式应该为 mid = l + r + 1 >> 1：

long l = 0, r = 1000009;
while (l < r) {
    long mid = l + r + 1 >> 1;
    if (check(mid)) {
        l = mid;
    } else {
        r = mid - 1;
    }
}

当当 check（mid） == true 调整的是 r 时：计算 mid 的方式应该为 mid = l + r >> 1：

long l = 0, r = 1000009;
while (l < r) {
    long mid = l + r >> 1;
    if (check(mid)) {
        r = mid;
    } else {
        l = mid + 1;
    }
}

力扣有一道经典题目:

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[]{-1, -1};
        int n = nums.length;
        if (n == 0) return ans;

        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] != target) {
            return ans;
        } else {
            ans[0] = l;
            l = 0; r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= target) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            } 
            ans[1] = l;
            return ans;
        }
    }
}