Binary search, is a fundamental algorithm in computer science. It allows you to perform efficient searches in ordered lists. Let's explore how it works:
- Binary search is applied to an ordered list (e.g. a list of numbers in ascending order).
- The algorithm repeatedly splits the list in half, reducing the possible locations of the searched element.
- Initially, we have the complete list.
- We calculate the index of the intermediate element of the list.
- We compare the middle element with the sought value.
- If the fetched value is equal to the middle element, we find the element and return its index.
- Otherwise, we check whether the fetched value is greater or less than the middle element.
- If it is larger, we repeat the process on the top half of the list; if it is smaller, in the lower half.
- We continue dividing the list until we find the element or determine that it is not present.
- Binary search is very efficient, as each iteration reduces the search space by half.
- Its complexity is O(log n), where n is the size of the list.
- Compared to linear search, which has O(n) complexity, binary search is significantly faster for large lists.