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

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

为了部分回答这个问题，可以分解出实际的比较（使用回调函数或类似函数），这取决于是要搜索比元素大的第一个元素还是要搜索的第一个元素较小的元素。但是，在第一个代码块中，您使用

arr[mid] <= val && arr[mid+1] > val

而在第二个块中，索引在第二个条件下移动

if (arr[mid] >= val && arr[mid] < val)

省略了，好像不一致

Answer 2

下面是一个通用算法，给定一个已排序的元素范围和一个值，它 returns 一对迭代器，其中第一个迭代器的值是排序范围中比较小的第一个元素比输入值大，第二个迭代器的值是该范围内比较大于输入值的第一个元素。

如果返回的迭代器对指向范围的末尾，则表示输入的范围为空。

我已尽可能使其通用化，并且它还可以处理边际情况和重复项。

template<typename BidirectionalIterator>
std::pair<BidirectionalIterator, BidirectionalIterator>
lowhigh(BidirectionalIterator first, BidirectionalIterator last,
        typename std::iterator_traits<BidirectionalIterator>::value_type const &val) {
  if(first != last) {
    auto low = std::lower_bound(first, last, val);
    if(low == last) {
      --last;
      return std::make_pair(last, last);
    } else if(low == first) {
     if(first != last - 1) {
        return std::make_pair(first, std::upper_bound(low, last - 1, val) + 1);   
      } else {
        return std::make_pair(first, first);  
      }
    } else {
      auto up = std::upper_bound(low, last, val);
      return (up == last)? std::make_pair(low - 1, up - 1) : std::make_pair(low - 1, up);
    }
  }
  return std::make_pair(last, last);
}

LIVE DEMO

Answer 3

编写正确的程序很难。一旦一个程序被验证是正确的，它就应该很少被修改，更多地被重用。在这一行中，鉴于您使用的是 C++ 而不是 C，我建议您尽可能地使用标准 C++ 库。您正在寻找的这两个功能都在算法中为您提供。

http://en.cppreference.com/w/cpp/algorithm/lower_bound http://en.cppreference.com/w/cpp/algorithm/upper_bound 为你施展魔法，鉴于模板的强大功能，你应该能够通过添加其他实现排序的方法来使用这些方法。

HTH.

Answer 4

您的搜索例程有一些错误 [一个被彻底破坏]。我已经对它们进行了一些清理，但我是从您的代码开始的。注意：不能保证——这里已经晚了，但这应该给你一个起点。请注意 "lo/hi" 是标准命名法（例如，lo 是您的开始，hi 是您的结束）。另外，请注意 hi/lo 设置为 mid 而 not mid+1 或 mid-1

有一些边缘情况需要应对。 while 循环必须是“<”，否则 "mid+1" 将运行超过数组末尾。

int
binarysearch_larger(const int *arr,int cnt,int val)
// arr -- array to search
// cnt -- number of elements in array
// val -- desired value to be searched for
{
    int mid;
    int lo;
    int hi;
    int match;

    lo = 0;
    hi = cnt - 1;

    match = -1;

    while (lo < hi) {
        mid = (hi + lo) / 2;

        if (arr[mid] <= val) && (arr[mid+1] > val)) {
            if ((mid + 1) < cnt)
                match = mid + 1;
            break;
        }

        if (arr[mid] > val)
            hi = mid;
        else
            lo = mid;
    }

    return match;
}

int
binarysearch_smaller(const int *arr,int cnt,int val)
// arr -- array to search
// cnt -- number of elements in array
// val -- desired value to be searched for
{
    int mid;
    int lo;
    int hi;
    int match;

    lo = 0;
    hi = cnt - 1;

    match = -1;

    while (lo < hi) {
        mid = (hi + lo) / 2;

        if (arr[mid] <= val) && (arr[mid+1] > val)) {
            match = mid;
            break;
        }

        if (arr[mid] > val)
            hi = mid;
        else
            lo = mid;
    }

    // the condition here could be "<=" or "<" as you prefer
    if ((match < 0) && (arr[cnt - 1] <= val))
        match = cnt - 1;

    return match;
}

Answer 5

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

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

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

请注意，不变量没有说明区间 [first、last] 的任何内容。在不进一步了解向量的情况下，唯一有效的限制初始化是 first = 0 和 last = 向量的最后位置。这满足条件，因为在 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 如果它存在，所以我们只必须检查我们是否仍在向量中。

考虑到这一点，您可以根据需要修改二进制搜索。让我们将其更改为找到小于 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;
}

检查我们是否仅更改了运算符（>= 而不是 >）和 return，使用与之前相同的参数。

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

Binary search for finding the lowest and largest element in a sorted array than a given value?

c++

algorithm

binary-search