二进制搜索查找排序数组中的最低和最大元素而不是给定值？

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的最后一个.我们改变了不变量:

首先之前的每个元素都小于x,并且最后一个元素大于或等于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;
}

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