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!
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments