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