二分查找的边界问题

刷LeetCode时看见一个很好的二分搜索题解，很好地讲了边界问题，记录一下，顺便多写了一个findUpper()函数
二分查找题解

#include
#include
using namespace std;



int findLower(vector& nums, int target) {
    int l,r,m;
    l = 0, r = nums.size() - 1;
    if(nums[r] < target)
    {
    	return nums.size();	//特殊判断，如果目标值大于数组最大值，就直接返回数组长度
	}

	//程序走到这里时，target不会大于数组最大值
    while(l < r)
    {
        m = (l + r) / 2;		//m是向下取整 
        if(nums[m] >= target)		//若最后没找到，nums[m]会是第一个大于target的数，所以最后的结果是大于等于target的最小数
            r = m;
        else
            l = m + 1;
    }
    return l;
}

int findUpper(vector& nums, int target) {
    int l,r,m;
    l = 0, r = nums.size() - 1;
    if(nums[l] > target)
    {
    	return 0;	//特殊判断，如果目标值小于数组最小值，就直接返回0
	}

	//程序走到这里时，target不会小于数组最小值
    while(l < r)
    {
        m = (l + r + 1) / 2;		//m是向上取整 
        if(nums[m] > target)		//若最后没找到，nums[m]会是第一个小于target的数，所以最后的结果是小鱼等于target的最大数
            r = m - 1;
        else
            l = m;
    }
    return l;
}

int main()
{
	vector nums = {1, 3, 3, 5, 6};
	cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5702341.html