Binary search, sorted array

Question

I learn about binary search, and the basic definition starts with an iterator with the first element and the other to the last. You also have a key, which is the element you are looking for. First, the key is compared with the midpoint value, and then the upper half or lower half is excluded depending on whether the key is larger or smaller than the midpoint value. And the process continues until a match is found.

Wouldn't this method require sorting the container you are viewing? Otherwise, I do not see how the comparison between the key and the values ​​in the container is to exclude parts of the container for viewing, any specific use.

Answer 1

Yes Yes.

In computer science, a binary search or semi-interval search search algorithm finds the position of a given input value (search keyword) in an array sorted by key value .

Source: Wikipedia: The binary search algorithm , although any other decent text in the algorithm should mention that the array must be sorted.

Answer 2

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

When you implement a binary search for a set, you must make sure that the set, if sorted first. Usually you sort the list first, and then always add the items to the right place (to make sure the new collection is still sorted). Assuming you also use binary search to find the right place to add, both append and search are O (log2 (N)) in the worst case.

When you consider various search algorithms, you should also consider the structure of the underlying data and the cost of adding an element to it.