Time ComplexityLesson 53Free preview
Binary Search
This lesson is part of DSA · All levels
Summary
Binary search is just O(log n) because each step throws out half the remaining range, so one million elements is about twenty comparisons. The best case is when the middle element directly matches. The recursive version requires a stack O(log n), while the iterative version is sufficient O(1).
Key points
- Time in the worst case.
- Every step throws half the range
- Best case when the mean is right
- Iterative of memory, recursive of stack
Full lesson
Code examples and quizzes
Full lessons, code examples, and quizzes are available to subscribers. 5 questions.