Brute Force, Bisection, or in: Timing Three Searches to 100 Million

Brute force, bisection or Python's in: which search barely notices a tenfold bigger list, and is the built-in one really a better algorithm?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Brute-force search, one element at a time

Brute force walks the list from the beginning to the end and asks each element a single question: is this the one? Write that loop yourself rather than leaning on the built-in: one check passes a list that raises an error if you ask it x in L, although a for loop over it works normally. Define is_in(L, x), returning True the moment an element equals x and False once the loop runs off the end.

def is_in(L, x):
    # Examine the elements of L one at a time, from the beginning to the end.
    return ...

def is_in(L, x):
    # Examine the elements of L one at a time, from the beginning to the end.
    return ...

Python runs in your browser

⌘/Ctrl + Enter runs

returns True for the first and for the last element

returns False for a missing element and for an empty list

stops looking as soon as it finds a match

walks the list itself instead of asking the built-in in

←Previous Which Parameter Costs Time? compound, sum_of, and One Linear Shape Next A Loop Inside a Loop: the diameter Function and Quadratic Growth →