在排序数组中查找比给定值最低和最大的元素的二分搜索？

Question

因此，我试图实现二分搜索算法（尽可能通用，以适应不同的情况）。我在网上搜索了一下，有的使用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;
    }
}

当我不得不为这样的抽象修改二分搜索时，我经常会感到超级困惑。请让我知道是否有更简单的方法相同？谢谢！

Answer 1

正如你所说的，有不同的方法来表达二分搜索的结束条件，它完全取决于你的两个极限的意思。让我来解释一下我的，我认为它很容易理解，而且它可以让你在其他情况下修改它，而不用考虑太多。

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

在最后一个之前的每个元素都大于x，而在第一个之前的每个元素都小于或等于（相反的情况）。

注意，不变量并没有说明间隔[first，last]。不需要进一步了解向量的限制的唯一有效初始化是first=0和last=向量的最后位置。这就满足了这样一个条件，即在最后一个之后没有任何东西，在第一个之前没有任何东西，所以一切都是正确的。

由于区间[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，如果它存在的话，所以我们只需要检查我们是否还在向量内。

记住这一点，您可以根据需要修改二进制搜索。让我们把它改成找到最后一个小于x的。我们改变不变量：

first之前的每个元素都小于x，last之后的每个元素都大于或等于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;
}