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!

Please tell me you've created a function for these tasks... post complete code. — Karoly Horvath
– Karoly Horvath, Commented Oct 31, 2015 at 18:58
It should return -1 if there is no such element. I get confused in writing such binary search hence I didn't know where to write it. How do I do it separately? — hans
– hans, Commented Oct 31, 2015 at 19:05

AlexAlvarez · Accepted Answer · 2015-11-01 14:52:41Z

17

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.

answered Nov 1, 2015 at 14:52

AlexAlvarez

8295 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

hans Over a year ago

this is so easy. You made it so simple. Kudos. Understood it so easily. Thanks a lot. :)

hans Over a year ago

going on the same lines, can you also post the code, if in case I want to find the first and last occurrence of an element in a sorted array containing duplicate values? I can do that, but my code involves recursion, I want to do it by your method.

AlexAlvarez Over a year ago

You can just use the two previous codes for that. For the first ocurrence, you take the "get_last_smaller" position + 1, as it's the only candidate position (of course you need to check if it's the proper value, otherwise say it doesn't exist). For the last ocurrence, just take "get_first_greater" - 1, checking again if the number is the proper one. In both cases don't forget to check if you're still in the vector.

hans Over a year ago

I have a doubt. Like you have done, you never really check the case if a[mid] == something, you just take two cases, either it's less than or greater than. I want to know, will your approach work in every case, or are their some where we do have to check against the middle value as well?

AlexAlvarez Over a year ago

I've coded many binary search variants and I always use this approach. But I can't promise it will work in every case, as maybe there's a problem I haven't considered so far.

Sudharshan Viswanathan · Accepted Answer · 2015-11-01 04:53:02Z

1

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.

answered Nov 1, 2015 at 4:53

Sudharshan Viswanathan

707 bronze badges

Comments

Codor · Accepted Answer · 2015-10-31 19:01:04Z

0

To answer the question in part, it would be possible to factor out the actual comparison (using a callback function or similar), depending on whether the first element which is larger than the element is to be searched or the first element which is smaller. However, in the first code block, you use

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

while in the second block, the index shift in the second condition

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

is omitted, which seems to be inconsistent.

answered Oct 31, 2015 at 19:01

Codor

17.6k9 gold badges32 silver badges59 bronze badges

Comments

Craig Estey · Accepted Answer · 2015-11-01 06:42:11Z

Your search routines had some bugs [one was outright broken]. I've cleaned them up a bit, but I started from your code. Note: no guarantees--it's late here, but this should give you a starting point. Note the "lo/hi" is standard nomenclature (e.g. lo is your start and hi is your end). Also, note that hi/lo get set to mid and not mid+1 or mid-1

There are edge cases to contend with. The while loop has to be "<" or "mid+1" will run past the end of the array.

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

Dimitrios Bouzas · Accepted Answer · 2015-11-01 20:30:58Z

0

Below is a generic algorithm that given a sorted range of elements and a value, it returns a pair of iterators, where the value of the first iterator is the first element in the sorted range that compares smaller than the entered value, and the value of the second iterator is the first element in that range that compares greater than the entered value.

If the pair of the returned iterators points to the end of the range it means that entered range was empty.

I've made it as generic as I could and it also handles marginal cases and duplicates.

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

edited Nov 1, 2015 at 20:30

answered Oct 31, 2015 at 20:28

Dimitrios Bouzas

43.1k11 gold badges103 silver badges177 bronze badges

3 Comments

Michael Burr Over a year ago

This code assumes that there are no duplicate elements in the array. And your assertion that "it's certainly faster than your version due to the fact that it handles marginal cases with out doing binary search" assumes that the searched item will lie at or outside the range of the array's contents more often than not. That may or may not be true. If it were always true, then your general purpose binary search library function would most likely do the same. Maybe you've just added several comparisons that would be better served dividing the array.

Dimitrios Bouzas Over a year ago

@MichaelBurr An enormous thanks for the review, all the comments where extremely accurate and the bugs well spotted. I corrected the language and the algorithm, now it handles duplicates as well. Once again thank you for taking the time spotting my idiotic mistakes.

Michael Burr Over a year ago

There was nothing idiotic, sorry if I came across as rude.

Collectives™ on Stack Overflow

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

5 Answers 5

5 Comments

Comments

Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

5 Comments

Comments

Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related