二进制搜索以获取第一个整数的位置> =搜索的整数

Question

在排序数组中,我需要找到第一个整数的位置> =给定的整数(如果数组中不存在这样的整数,则应返回-1).二元搜索的以下修改是否正确解决问题？我使用了不少测试用例来验证功能,但仍想确认.

n =不.数组中的元素

ele =要搜索的整数

int binarySearch(int a[],int n,int ele)
{
  int lower=0;
  int upper=n-1;

  int mid;
  int pos=-1;
  while(lower<=upper)
  {
    mid=(lower+upper)/2;
    if (a[mid]==ele)
    {
        while(mid>=0 && a[mid]==ele)
            mid--;
        return mid+1;
    }
    else if(a[mid]<ele)
        lower=mid+1;
    else
    {
        pos=mid;
        upper=mid-1;
    }
  }
  return pos;
}

Answer 1

你写的不是二元搜索; 在最坏的情况下,它是线性搜索.(考虑当数组包含所有相同元素时会发生什么).

信不信由你,正常的二进制搜索将完全符合您的要求(找到大于或等于目标的最小整数),因为它是正确编程的.

我们可以在一些不变量的帮助下对它进行编程.

• 0 <= lo <= hi <= n
• a[0..lo) < x
• a[hi..n) >= x

其中x是目标元素,a[0..lo) <= x意味着半开区间的所有元素[0..lo)都小于x.

lo并且hi是下限和上限,并且首先,它们将是0并且n使得不变量中的两个范围最初都是空的.

所以现在算法:

int 
binarySearch(int a[], int n, int x)
{
    int lo = 0, hi = n;

    while(lo < hi)
    {
        int mid = lo + (hi - lo)/2;

        if(a[mid] < x) lo = mid + 1;
        else           hi = mid;
    }

    return hi;
}

因此,正文只是一个标准的二元搜索体,包含了非溢出计算mid.

决定哪个lo和哪个hi应该分配mid也直接来自不变量:

• 如果a[mid] < x那么a[mid]应该在范围内a[0..lo)如此lo = mid + 1.
• 相反,如果a[mid] >= x,那么a[mid]属于a[hi..n)那样hi = mid.

return语句也是不言自明的,因为给定的不变量是满足a[hi]的最小元素.aa[i] >= x

接下来要看的最后一件事就是while循环中的条件,具体来说,如果lo >= hi考虑到不变量,那么这个循环将会停止lo = hi.此时a[lo..hi)为空,表示搜索空间已耗尽.

此实现的接口与您指定的接口略有不同,因为如果数组中没有此类元素,则它将范围a[hi..n)视为空,这在何时为真hi = n.这意味着它不是返回-1,而是返回n,这很容易检查,但如果你想让它返回,-1只需用以下命令替换return语句:

return hi < n ? hi : -1;