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

本是古典何须时尚 2024-03-26 19:01 52阅读 0赞

## 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函数 ##

## ![cb04c404d02c4199a7ae3e32f7841ff1.png][] ##

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;
            }
        }
    }

[cb04c404d02c4199a7ae3e32f7841ff1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/0590e11f67e8456a8207cadd1a13a29a.png