binary search, 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. Binary search 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 until it is successful. If the search ends with the remaining half being empty, the target is not in the array.
Implementation in over 20+ languages: here
Ask our coding community anything.
How this works?
This algorithm takes advantage of the fact that the elements are sorted.
Steps:
- Compare x with the middle element.
- If x matches with the middle element, return the mid index.
- If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
- (x is smaller) recur in the left half.
| Complexity | Notation |
|---|---|
| Worst-case performance | O(log n) |
| Best-case performance | O(1) |
| Average performance | O(log n) |
| Worst-case space complexity | O(1) |
