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

Question

So, I was trying to implement the binary search algorithm (as generic as possible which can adapt to different cases). I searched for this on the internet, and some use, while (low != high) and some use, while (low <= high) and some other different condition which is very confusing.

Hence, I started writing the code for finding the first element which is greater than a given element. I wish to know if there is a more elegant solution than this?

Main code:

#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;
    }
}

Similarly, for finding the first element which is smaller than the given element,

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;
    }
}

I often get super confused when I have to modify binary search for such abstraction. Please let me know if there is simpler method for the same? Thanks!

Answer 1

As you say, there are different ways to express the end condition for binary search and it completely depends on what your two limits mean. Let me explain mine, which I think it's quite simple to understand and it lets you modify it for other cases without thinking too much.

Let me call the two limits first and last. We want to find the first element greater than a certain x. The following invariant will hold all the time:

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

Notice that the invariant doesn't say anything about the interval [first, last]. The only valid initialization of the limits without further knowledge of the vector is first = 0 and last = last position of the vector. This satisfies the condition as there's nothing after last and nothing before first, so everything is right.

As the interval [first, last] is unknown, we will have to proceed until it's empty, updating the limits in consequence.

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;
}

As you can see, we only need two cases, so the code is very simple. At every check, we update the limits to always keep our invariant true.

When the loop ends, using the invariant we know that last + 1 is greater than x if it exists, so we only have to check if we're still inside our vector or not.

With this in mind, you can modify the binary search as you want. Let's change it to find the last smaller than x. We change the invariant:

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

With that, modifying the code is really easy:

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;
}

Check that we only changed the operator (>= instead of >) and the return, using the same argument than before.

Answer 2

It is hard to write correct programs. And once a program has been verified to be correct, it should have to be modified rarely and reused more. In that line, given that you are using C++ and not C I would advise you to use the std C++ libraries to the fullest extent possible. Both features that you are looking for is given to you within algorithm.

http://en.cppreference.com/w/cpp/algorithm/lower_bound http://en.cppreference.com/w/cpp/algorithm/upper_bound does the magic for you, and given the awesome power of templates you should be able to use these methods by just adding other methods that would implement the ordering.

HTH.