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

标签 c binary-search

在排序数组中,我需要找到第一个整数的位置 >= 给定整数(如果数组中不存在这样的整数,则应返回 -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;
}

最佳答案

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

信不信由你,如果编程正确,普通的二分查找将完全按照您的要求进行(找到大于或等于目标的最小整数)。

我们可以借助一些不变量对其进行编程。

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

哪里x是目标元素,a[0..lo) <= x表示[0..lo)的半开区间内的所有元素小于 x .

lohi是下限和上限,首先,它们将是 0n这使得不变量中的两个范围最初都是空的。

现在算法:

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]a 中的最小元素满意a[i] >= x .

然后最后要看的是while循环中的条件,具体来说,如果lo >= hi,这个循环就会停止。考虑到不变量,只有在 lo = hi 时才会发生.在哪一点a[lo..hi),表示搜索空间已用完。

此实现的接口(interface)与您指定的略有不同,因为如果数组中没有这样的元素,那么它将处理范围 a[hi..n)为空,当 hi = n 时为真.这意味着不是返回 -1 , 它返回 n , 这同样容易检查,但如果你想让它返回 -1只需将 return 语句替换为:

return hi < n ? hi : -1;

关于c - 二进制搜索以获取第一个整数的位置 >= 搜索到的整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21114459/

相关文章:

algorithm - 为了更快速地搜索,难道不应该在进行二分搜索之前对数据应用合并排序,还是直接跳到线性搜索?

c - 结构会自动分解到内存位置吗?

c - 如何将运行时变量替换为 c 中的字符串?

c++ - C/C++ 检查是否设置了一位,即 int 变量

java - 我不可能理解所描述的字符串搜索方法。什么是 uFFFF?

python - 查找数组中缺失的元素

Java 比较三个字符串数组并使用 Binarysearch

c - 静态变量未初始化为零

python - 使用python发送unsigned char

java - 整数域到定域映射数组的应用与实现