Binary Search is a searching algorithm for sorted lists, and it works by comparing the search key value with the key value of the middle element of the list. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element’s key, then the algorithm repeats its action on the sublist to the left of the middle element or, if the search key is greater, on the sublist to the right. If the remaining list to be searched is empty, then the key value is not present in the list.
[Example] [Example]
[Resource] [Resource]
Performance | |
---|---|
Worst case performance | O(log n) |
Best case performance | Ω(1) |
Average case performance | O(log n) |