Binary Search Time Complexity (Big-O)
Binary search runs in O(log n) average and worst case, O(1) best case, with O(1) space. It finds an element in a sorted array by repeatedly halving the search interval.
Open the interactive DevRef Hub tool →Key facts
| Best | O(1) |
|---|---|
| Average | O(log n) |
| Worst | O(log n) |
| Space | O(1) |
Frequently asked questions
What is the time complexity of binary search?
O(log n) in the average and worst case.
Does binary search need a sorted array?
Yes, the array must be sorted for the halving to be correct.
Related pages
Big-O of Binary Search is part of DevRef Hub on GOAT Lab — a free reference you can use without signing up, and it works offline. Open the tool above for any custom value.
Part of GOAT Lab — 26 free, browser-based science, engineering and developer tools. No sign-up.