修改二进制搜索中的无限循环-Java 学习之路

我正在尝试实现二进制搜索的修改版本，它从已排序的数组返回给定键的下一个最大值的位置 .

这是代码 - （lli指long long int）

lli search(vector<lli>arr,lli key)
{
    lli low=0,high=arr.size() - 1,mid,pos=-1;

    while(low<=high)
    {
        mid=low + (high-low)/2;

         if(arr[mid]<key)
            low=mid+1;
        else{
                pos=mid;
                high=mid-1;
            }
    }
    return pos;
}

这里arr是排序数组，我们必须找到下一个最大元素的位置而不是数组arr中的键 .

我已经注意到键在[min（arr），max（arr）]之间 . 所以，pos将在[0，arr.size（） - 1]中有一个值 .

该方法针对我能想到的许多值运行，但在线判断以时间限制超出错误拒绝它 . 这里有无限循环吗？

1 回答

你可以解决为常规二进制搜索但使用

if (arr[mid] == key){
    if (mid == arr.size() - 1)
         return -1; // key was the last element, there is nothing after it
    return mid + 1;
}

回复于 2024-05-02T06:44:40+08:00

修改二进制搜索中的无限循环

1 回答

相关问题