Binary search, sorted array

Question

I'm learning about binary search and the basic definition starts with an iterator to the first element and another one to the last. You also have a key, which is the element you are looking for. The key is compared to the value of the midpoint first and then upper half or lower half is eliminated depending on whether the key is larger or smaller than the value of the midpoint. And the process continues until there is a match.

Wouldn't this method require that the container you are looking through is sorted? Otherwise I don't see how the comparison between the key and values in the container to eliminate portions of the container to look through is any particular use.

Yes, binary search only works on sorted collections. Any article on it which doesn't specify that is inadequate :( — Jon Skeet
– Jon Skeet, Commented Sep 9, 2013 at 14:41
Who is downvoting this? The question is clear, includes motivation, demonstrates understanding, and is clearly relevant to coding. "I know this, how can anyone not know this" is not an adequate reason to downvote questions. — us2012
– us2012, Commented Sep 9, 2013 at 14:43
@us2012 it is about not doing enough research before asking a question. almost all the articles related to binary search will mention this very clearly — Saksham
– Saksham, Commented Sep 9, 2013 at 14:46
@Saksham. I only asked the question because I was skimming through one of the many technical interview programming books and in the particular book I was looking at, it had not been mentioned. Of course I am sure the author assumed knowledge of the fact but that is one example where it was not mentioned. — Mars
– Mars, Commented Sep 9, 2013 at 17:16

Joni · Accepted Answer · 2013-09-09 14:42:03Z

4

Yes, it does.

In computer science, a binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value.

Source: Wikipedia: Binary Search Algorithm, though any other decent text on the algorithm should mention the array must be sorted.

answered Sep 9, 2013 at 14:42

Joni

112k14 gold badges151 silver badges201 bronze badges

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

Comments

trungdinhtrong · Accepted Answer · 2013-09-09 14:58:24Z

The answer is yes. The binary search assume that you sort your set first. If I am not wrong, any search algorithm with performance better than O(N) required that your set is stored in some special data structure (sorted list, binary tree, red-black tree...).

When you implement a binary search for a set, you have to make sure that the set if sorted first. Usually you would sort the list first and then always add elements in the right place (to make sure that the new set is still sorted). Assuming you also use binary search to find the right the place to add, both adding and searching is O(log2(N)) in the worst case scenario.

When you consider different search algorithms, you must also consider the underlying data structure and the cost to add element into it.

Collectives™ on Stack Overflow

Binary search, sorted array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related