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?
Hope this will help…
You can read the description of the return value here!!
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.
arr[l] is the largest element smaller than the key and arr[r] is the smallest element larger than the key…hope this helps…
Thanks for asking this question, was just searching for it on internet…
Can you please tell me why isn’t this piece working
ohhkk thanks @kunal361
And one more question, should array need to be sorted to use lower_bound() method??
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!!!
Of course it helped! 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.
Can u provide the problem link?? Also if this has answered your question…can I close this thread??
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.