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.

Answer 1

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.

Answer 2

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.