You are not logged in. Please login at www.codechef.com to post your questions!

×

[closed] Binary search function - STL

2
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?

asked 29 Nov '14, 18:50

sandy999's gravatar image

2★sandy999
39111638
accept rate: 10%

closed 01 Dec '14, 18:03

kunal361's gravatar image

4★kunal361
6.0k133272

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

(29 Nov '14, 20:56) rishabhprsd72★

The question has been closed for the following reason "The question is answered, right answer was accepted" by kunal361 01 Dec '14, 18:03


Hope this will help...:)

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

link

answered 29 Nov '14, 19:51

kunal361's gravatar image

4★kunal361
6.0k133272
accept rate: 21%

edited 29 Nov '14, 20:15

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


(29 Nov '14, 21:19) rishabhprsd72★

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

(29 Nov '14, 22:03) kunal3614★

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

(29 Nov '14, 22:05) rishabhprsd72★

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!!!

(29 Nov '14, 22:09) kunal3614★

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...:)

link

answered 30 Nov '14, 18:20

kunal361's gravatar image

4★kunal361
6.0k133272
accept rate: 21%

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.

(01 Dec '14, 16:32) sandy9992★

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

(01 Dec '14, 18:01) kunal3614★
1

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.

(01 Dec '14, 18:03) sandy9992★

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.

link

answered 30 Nov '14, 17:38

sandy999's gravatar image

2★sandy999
39111638
accept rate: 10%

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,056
×279

question asked: 29 Nov '14, 18:50

question was seen: 4,024 times

last updated: 01 Dec '14, 18:03