Binary Search algorithm

Question

I'm using binary search to locate a record. My question is not about whether the data is present or not. I'll list my questions below.

if data are in following order

1 2 3 4 4 5 5 5 6 7 8 8 9 10 11

If now i want to search 5 where it is locate first. By using binary search algorithm I can get the 5 is present or not. in the above case i can get the 6th location of 5( totally 13 data) . But I need to get 5th location. How can i get this using binary search ? Once again in some cases i need to get last position of the given data. How can i get this binary search algorithm.

Is there any fastest method than binary search ? Not but hashing method ?

Angelom · Accepted Answer · 2011-10-21 08:34:04Z

4

You could use a binary search again.

To get the lowest value of 5, start the search again but with its upper bounds 1 less than the current found value of 5.
To get the higest value of 5, start the search again but with its lower bounds 1 greater than the current found value of 5.

You must repeat the process above until you can no longer find the item, when you can no longer find the item, the last item found was the one you were looking for.

edited Oct 21, 2011 at 8:34

answered Oct 20, 2011 at 6:47

Angelom

2,5411 gold badge15 silver badges8 bronze badges

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

1 Comment

Angelom Over a year ago

Made a change, if you are happy, mark the question as answered.

Collectives™ on Stack Overflow

Binary Search algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related