gpt4 book ai didi

c++ - 二进制搜索查找排序数组中比给定值最小和最大的元素?

转载 作者:太空狗 更新时间:2023-10-29 19:48:06 24 4
gpt4 key购买 nike

因此,我尝试实现二分查找算法(尽可能通用,以适应不同的情况)。我在网上搜索了这个,有些用处,while (low != high)还有一些用途,while (low <= high)以及其他一些非常令人困惑的不同情况。

因此,我开始编写代码以查找大于给定元素的第一个元素。我想知道是否有比这更优雅的解决方案?

主要代码:

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <climits>
#include <set>
#include <cstring>

using namespace std;
int arr1[2000];
int n;
int main (void)
{
int val1,val2;
cin>>n;
for (int i = 0; i < n; i++)
cin>>arr1[i];
sort(arr1,arr1+n);
cout<<"Enter the value for which next greater element than this value is to be found";
cin>>val1;
cout<<"Enter the value for which the first element smaller than this value is to be found";
cin>>val2;

int ans1 = binarysearch1(val1);
int ans2 = binarysearch2(val2);

cout<<ans1<<"\n"<<ans2<<"\n";
return 0;
}
int binarysearch1(int val)
{
while (start <= end)
{
int mid = start + (end-start)/2;
if (arr[mid] <= val && arr[mid+1] > val)
return mid+1;
else if (arr[mid] > val)
end = mid-1;
else
start = mid+1;
}
}

类似地,为了找到第一个小于给定元素的元素,

int binarysearch2(int val)
{

while (start <= end)
{
int mid = start + (end-start)/2;
if (arr[mid] >= val && arr[mid] < val)
return mid+1;
else if (arr[mid] > val)
end = mid-1;
else
start = mid+1;
}
}

当我不得不为这种抽象修改二进制搜索时,我常常感到非常困惑。请让我知道是否有更简单的方法?谢谢!

最佳答案

如您所说,二分查找的结束条件有不同的表达方式,这完全取决于您的两个限制的含义。让我解释一下我的,我认为这很容易理解,它可以让您针对其他情况修改它而无需考虑太多。

让我称这两个限制为第一个最后一个。我们想找到第一个大于某个 x 的元素。以下不变量将始终成立:

Every element past last is greater than x and every element before first is smaller or equal (the opposite case).

请注意,不变量没有说明区间 [first, last]。在不进一步了解 vector 的情况下,唯一有效的限制初始化是 first = 0 和 last = vector 的最后位置。这满足条件,因为 last 之后没有任何内容,first 之前也没有任何内容,所以一切都是正确的。

由于区间 [first, last] 未知,我们将不得不继续进行直到它为空,从而更新限制。

int get_first_greater(const std::vector<int>& v, int x)
{
int first = 0, last = int(v.size()) - 1;
while (first <= last)
{
int mid = (first + last) / 2;
if (v[mid] > x)
last = mid - 1;
else
first = mid + 1;
}
return last + 1 == v.size() ? -1 : last + 1;
}

如您所见,我们只需要两种情况,所以代码非常简单。在每次检查时,我们都会更新限制以始终保持我们的不变量为真。

当循环结束时,使用不变量我们知道 last + 1 大于 x 如果它存在,所以我们只需要检查我们是否仍然是否在我们的 vector 中。

考虑到这一点,您可以根据需要修改二进制搜索。让我们更改它以找到小于 x 的最后一个。我们改变不变量:

Every element before first is smaller than x and every element after last is greater or equal than x.

有了它,修改代码就真的很容易了:

int get_last_smaller(const std::vector<int>& v, int x)
{
int first = 0, last = int(v.size()) - 1;
while (first <= last)
{
int mid = (first + last) / 2;
if (v[mid] >= x)
last = mid - 1;
else
first = mid + 1;
}
return first - 1 < 0 ? -1 : first - 1;
}

检查我们是否仅更改了运算符(>= 而不是 >)和返回值,使用与之前相同的参数。

关于c++ - 二进制搜索查找排序数组中比给定值最小和最大的元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33455341/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com