Log in from a computer to take this course

You'll need to log in from a computer to start How to Implement Search Algorithms with Python. But you can practice or keep up your coding streak with the Codecademy Go app. Download the app to get started.

apple storegoogle store
Learn

How efficient is binary search?

In each iteration, we are cutting the list in half. The time complexity is O(log N).

A sorted list of 64 elements will take at most log2(64) = 6 comparisons.

In the worst case:

  • Comparison 1: We look at the middle of all 64 elements

  • Comparison 2: If the middle is not equal to our search value, we would look at 32 elements

  • Comparison 3: If the new middle is not equal to our search value, we would look at 16 elements

  • Comparison 4: If the new middle is not equal to our search value, we would look at 8 elements

  • Comparison 5: If the new middle is not equal to our search value, we would look at 4 elements

  • Comparison 6: If the new middle is not equal to our search value, we would look at 2 elements

When there’s 2 elements, the search value is either one or the other, and thus, there is at most 6 comparisons in a sorted list of size 64.

Instructions

A sorted data-set speeds up searching by a significant amount!

Without any knowledge about the ordering, we would resort to a linear search taking O(N) time.

Sign up to start coding

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?