Python DSALesson 104Free preview
Binary Search
This lesson is part of Python · All levels
Summary
This lesson describes binary search, a search algorithm that works by splitting two search ranges repeatedly. The main requirement is that the data must be sorted, and in return the search only requires O(log n) steps. You're going to learn both iterative and recursive versions of this algorithm.
Key points
- Binary search can only be used on data that's already sorted.
- Each step compares the target to the middle element and then throws out half the rest of the data.
- Time complexity is much faster than that of big data.
- The iterative version uses two low and high markers, the recursive version calls itself on the subarray.
- A null target is usually marked with a return of −1 or None.
Full lesson
Code examples and quizzes
Full lessons, code examples, and quizzes are available to subscribers. 5 questions.