Binary search function - STL

general
,
1

I have created a simple array (not a vector, template, class…nothing of that sort) and I want to use a nice and neat binary search function from the stl to find a particular value in the array and return its index.

Oh yes, the first thing I did is google “binary search function stl.” And voila! So many results. But everything involves Random iterator, template, class, forward iterator etc and since I haven’t learnt the OOPS part of C++ yet (Not that I am shying away from it, but I am just trying to put my Non-OOP knowledge to work), I am unable to comprehend those complicated terms.

Just like how for sorting an array, all I have to have is sort(Arr,Arr+N); with an algorithm header on top, could someone suggest a similar simple away of using the binary search function to find an element and return its index in this simple array of mine?

2 Likes
2

Hope this will help…:slight_smile:

You can read the description of the return value here!!

1 Like
3

Thanks for asking this question, was just searching for it on internet…

4

Hey @kunal361

Can you please tell me why isn’t this piece working

int main()
{
    int arr[]={9,77,3,4,5,6,7,8,9};
    sort(arr.begin(),arr.end());
    cout<<lower_bound(arr,arr+9,77)-arr;
    return 0;
}
5

Begin and end are not for arrays…I feel…check this out…http://ideone.com/CWDWL1

6

ohhkk thanks @kunal361

And one more question, should array need to be sorted to use lower_bound() method??

7

Yes…it uses binary search…also u can go through upper_bound…it gives the last index of the key…lower_bound returns the first index!!!

8

Thank you so much @kunal361

This is a kind of follow up question.

Suppose the element ‘a’ is not present in my simple array. But instead, I am looking for an element ‘b’ which is nearest to ‘a’ and just less than ‘a’. Also, I am looking for an element ‘c’ which is nearest to ‘a’ and just more than ‘a’. How do I tweak binary search to implement this?

I don’t need an STL function, but a general procedure as I am unable to understand the behaviour of the mid value in the binary search implementation to make sure the above thing works.

9

When r-l=1

arr[l] is the largest element smaller than the key and arr[r] is the smallest element larger than the key…hope this helps…:slight_smile:

1 Like
10

Of course it helped! :slight_smile: Thank you soo sooo much! I asked this question because I wanted to implement this idea of binary search in a ZCO 2012 problem WORMHOLES (I’ve never used binary search in a question before, always pulled on with linear search) although I haven’t completely got the problem right yet.

11

Can u provide the problem link?? Also if this has answered your question…can I close this thread??

12

I have posted it as a separate query as part of discussion on the same problem. It’s here http://discuss.codechef.com/questions/56739/zco-2012-problem-wormholes And yeah please close this thread.

1 Like