Binary search algorithm
Introduction
Binary search algorithm, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. Binary search runs in logarithmic time in the worst case, making O(log n) comparisons, where n is the number of elements in the array.
Overview
Binary search works on sorted arrays. Binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less or more than the middle element, the search continues in the lower or upper half of the array respectively, again taking the middle element to compare to the target value, and repeating this until the target value is found. This is achieved by keeping track of the array indices while dividing the array.
Algorithm
The binary search algorithm can be written as follows:
1. Find the middle element of the array. If the array has an even number of elements, the middle element is the element at the index (n-1)/2, where n is the number of elements in the array. If the array has an odd number of elements, the middle element is the element at the index n/2.
2. If the target value is equal to the middle element, return the index of the middle element.
3. If the target value is less than the middle element, repeat the process with the lower half of the array.
4. If the target value is greater than the middle element, repeat the process with the upper half of the array.
5. If the target value is not found after exhausting all elements in the array, return -1 or some other value that indicates that the target value was not found.
Complexity
The time complexity of binary search is O(log n), where n is the number of elements in the array. This is because with each comparison, the algorithm eliminates half of the remaining elements from consideration. The space complexity of binary search is O(1), as it requires only a constant amount of additional space.
Applications
Binary search is used in a wide variety of applications. It is used in computer science for search algorithms and database methodologies. It is also used in mathematical algorithms to find roots of functions, and in numerical analysis to solve problems such as the eigenvalue problem.
Variants
There are several variants of the binary search algorithm. These include:
1. Interpolation search: This is a variant of binary search that, instead of dividing the array into two equal-sized halves, estimates the position of the target value, assuming an uniform distribution of the values in the array.
2. Exponential search: This is a variant of binary search that is used when the array is unbounded or the size of the array is unknown.
3. Fractional cascading: This is a technique that speeds up binary searches for the same value in multiple sorted lists.
4. Uniform binary search: This is a variant of binary search that uses a tabulated sequence of probe positions to perform searches in a manner that is efficient on modern computer architectures.