java - 如何在二分查找中找到数组的最后一个元素

Question

在二分查找算法中，上界元素是array.length-1，那么如何找到数组的最后一个元素呢？

如果长度为 8 的数组元素的下限和上限分别为 6 和 7，那么我的中间元素为:

mid=(6+7)/2 即java中的6

Answer 1

这实际上取决于使用正确的比较和正确选择的中点。例如(没有变量类型声明)，

binsearch(a,val,left,right){
    if(left==right) return left;
    mid = (left+right)/2;
    if(a[mid] < val)
        return binsearch(a,val,mid+1,right);
    else
        return binsearch(a,val,left,mid);
}

将为您提供与 val 匹配的最左边元素的索引(即使它是数组中最右边的元素)。您不需要显式检查最后两个或向上舍入，而是使用内置的整数截断。

但是，如果您希望最右边元素的索引等于 val，那么您需要将 < 运算符更改为 >，并且 mid 应由下式给出

mid = (left+right+1)/2;

就这么简单。

编辑:还有一件事，我查看了为此使用的代码，并意识到您还必须更改对 binsearch 的调用以最终到达最右侧的元素。我将发布完整的代码(我应该首先完成)。这是一个二分搜索，用于查找等于 val 的最右边的元素。

binsearch(a,val,left,right){
    if(left==right) return left;
    mid = (left+right+1)/2;
    if(a[mid] > val)
        return binsearch(a,val,left,mid-1);
    else
        return binsearch(a,val,mid,right);
}