Computer science foundations · 10 minutes
Linear and binary search
Compare linear and binary search for finding a number in a list. State binary search's prerequisite and trace one small example.
Study · reference notes
Describe linear search
Linear search checks items one at a time. In the worst case it checks all n items; it does not require sorted data.
State the prerequisite
Binary search requires an ordered search space. Comparing the target with a middle item identifies which half can be discarded.
Explain halving
Binary search repeatedly halves the remaining interval until it finds the target or the interval is empty. Its worst-case number of comparisons grows logarithmically with n.
Independent lesson notes · independent tutor review pending
Sign in to save drafts, receive feedback and schedule reviews. Tutors see only work you submit to their assignments.
Sign in to practice