Linear Search and Binary Search: Counting the Checks

Beginner35 min3 exercises45 XP

Prerequisites

Python Lists: Create, Access, Modify, and Loop Through Lists Python For Loops: Iterate Over Anything with Examples Python While Loops: When For Loops Aren't Enough Python Functions: Define, Call, and Return Values

0/3 exercises

Searching a list means checking elements until you find the one you want, and the method you choose decides whether that takes 3 checks or 3 million. Linear search works on any list. Binary search is far faster on big lists, but it only works when the data is sorted.

What does it mean to traverse a list?

To traverse a list is to visit its elements one by one with a loop. A complete traversal visits every element, for example to add up all the scores. A partial traversal visits only some of them, for example stopping as soon as you find the first score below 50.

The exam's loop for traversing a list is FOR EACH. The variable item takes the value of each element in order, from the first to the last, and the block runs once for each value:

Pseudocode: average of a list (a complete traversal)

Run it

total ← 0
FOR EACH temp IN temps
{
  total ← total + temp
}
average ← total / LENGTH(temps)

LENGTH(temps) is the number of elements, so dividing the total by it gives the average. This is a complete traversal: the loop cannot skip any temperature without getting the wrong total.

Some traversal algorithms are worth knowing by heart because so many problems are built from them: finding the minimum or maximum value in a list, and computing the sum or average of a list of numbers. Python's for item in items: is the same loop as FOR EACH:

Complete and partial traversals

temps = [24, 27, 31, 29, 33, 26, 22] # a week of daily highs in °C

# Complete traversal: every element is visited.

total = 0

hottest = temps[0]

coldest = temps[0]

for t in temps:

total += t

if t > hottest:

hottest = t

if t < coldest:

coldest = t

print(f"Average {total / len(temps):.1f}, hottest {hottest}, coldest {coldest}")

# Partial traversal: stop at the first day above 30°C.

day = 0

for t in temps:

day += 1

if t > 30:

print(f"First day above 30°C: day {day} ({t}°C)")

break

Output

Average 27.4, hottest 33, coldest 22
First day above 30°C: day 3 (31°C)

How does linear search work?

Linear search, also called sequential search, checks each element of a list in order until it finds the value it wants or runs out of elements. It is how you look for a friend's name on an unsorted sign-up sheet: start at the top and read down.

Pseudocode: linear search

Run it

PROCEDURE contains(aList, target)
{
  FOR EACH item IN aList
  {
    IF(item = target)
    {
      RETURN(true)
    }
  }
  RETURN(false)
}

RETURN ends the procedure at once, so a match stops the search early: that is a partial traversal. Only when the loop finishes without a match does the procedure return false. This version also counts how many elements it checks:

Linear search, counting the checks

def linear_search(items, target):

checks = 0

for item in items:

checks += 1

if item == target:

return True, checks

return False, checks

roster = ["Maya", "Leo", "Priya", "Sam", "Ava", "Diego", "Kai", "Zoe"]

for name in ["Maya", "Ava", "Zoe", "Omar"]:

found, checks = linear_search(roster, name)

print(f"{name}: found = {found}, checks = {checks}")

Output

Maya: found = True, checks = 1
Ava: found = True, checks = 5
Zoe: found = True, checks = 8
Omar: found = False, checks = 8

The best case is 1 check, when the target is first. The worst case is checking every element: when the target is last, or not there at all. With 8 names that is 8 checks; with a million names it is a million. On the plus side, linear search works on any list, sorted or not.

How does binary search work?

Think of the guessing game where a friend picks a number from 1 to 100 and answers "higher" or "lower". The smart first guess is 50. Whatever the answer, half of the numbers are ruled out with one question.

Binary search does exactly that with a sorted list. It starts at the middle element. If that is the target, it is done. If the target is smaller, the middle and everything after it are eliminated; if the target is larger, the middle and everything before it are eliminated. The search repeats on the half that is left until it finds the value or every element has been eliminated.

Run this trace on a sorted list of 15 locker numbers:

Binary search, step by step

def binary_search(items, target):

low, high = 0, len(items) - 1

checks = 0

while low <= high:

mid = (low + high) // 2

checks += 1

print(f" check {checks}: middle is {items[mid]}, {high - low + 1} left")

if items[mid] == target:

return f"found after {checks} checks"

if target < items[mid]:

high = mid - 1 # drop the middle and everything after it

else:

low = mid + 1 # drop the middle and everything before it

return f"not in the list ({checks} checks)"

lockers = [3, 8, 12, 17, 21, 26, 30, 34, 41, 47, 52, 58, 63, 70, 77]

for target in [52, 4]:

print(f"Searching for {target}:")

print(" ", binary_search(lockers, target))

Output

Searching for 52:
  check 1: middle is 34, 15 left
  check 2: middle is 58, 7 left
  check 3: middle is 47, 3 left
  check 4: middle is 52, 1 left
  found after 4 checks
Searching for 4:
  check 1: middle is 34, 15 left
  check 2: middle is 17, 7 left
  check 3: middle is 8, 3 left
  check 4: middle is 3, 1 left
  not in the list (4 checks)

Fifteen elements, and binary search needed at most 4 checks, found or not. You can also watch both searches move through a list in the visualizer: linear search and binary search.

How do you trace binary search by hand?

Exam lists count positions from 1, so trace with positions. Write down which positions are still in play, find the middle one, compare, and cross out half. Here is a search for 63 in the 15 locker numbers above:

Check	Positions in play	Middle position	Middle value	Decision
1	1 to 15	8	34	63 is larger: keep 9 to 15
2	9 to 15	12	58	63 is larger: keep 13 to 15
3	13 to 15	14	70	63 is smaller: keep 13 to 13
4	13 to 13	13	63	found

The middle position is the average of the first and last positions in play. When an even number of positions is left, say 9 to 14, the average is 11.5. This trace rounds down to 11; rounding up also works, as long as you do it the same way every time. If the value is missing, the positions in play shrink until none are left, and the search reports that the value is not in the list.

How many iterations does binary search need?

Each check throws away about half of the elements that are left. So the most checks binary search can need is the number of times you can halve the list before nothing is left. A pencil-and-paper method: write the list size, halve it (drop any remainder), and keep going until you reach 0. Count the numbers you wrote before 0.

For 100 elements: 100, 50, 25, 12, 6, 3, 1. That is 7 numbers, so binary search needs at most 7 checks. Linear search could need all 100.

Sorted list size	Most checks: binary search	Most checks: linear search
7	3	7
15	4	15
100	7	100
1,000	10	1,000
1,000,000	20	1,000,000

Notice the pattern: doubling the size of the list adds only one more check to binary search, while linear search's worst case doubles. The program below measures the worst case by searching for every value in the list and every value that is missing:

Worst-case checks, measured

def binary_checks(items, target):

low, high, checks = 0, len(items) - 1, 0

while low <= high:

mid = (low + high) // 2

checks += 1

if items[mid] == target:

break

if target < items[mid]:

high = mid - 1

else:

low = mid + 1

return checks

print("List size | linear worst | binary worst")

for size in [10, 100, 1000, 10000]:

items = list(range(0, 2 * size, 2)) # sorted even numbers

worst = 0

for target in range(-1, 2 * size + 1): # present and missing values

worst = max(worst, binary_checks(items, target))

print(f"{size:>9} | {size:>12} | {worst:>12}")

Output

List size | linear worst | binary worst
       10 |           10 |            4
      100 |          100 |            7
     1000 |         1000 |           10
    10000 |        10000 |           14

Why must the data be sorted?

Binary search decides which half to throw away by comparing the target with the middle element. That only makes sense if every smaller value is on the left and every larger value is on the right. Data must be in sorted order to use binary search. On an unsorted list it can throw away the half that holds the answer:

Binary search on unsorted data gives wrong answers

def binary_search(items, target):

low, high = 0, len(items) - 1

while low <= high:

mid = (low + high) // 2

if items[mid] == target:

return True

if target < items[mid]:

high = mid - 1

else:

low = mid + 1

return False

scores = [88, 42, 97, 15, 63, 71, 29] # not sorted

print("Is 97 in the list?", 97 in scores)

print("Binary search on the unsorted list:", binary_search(scores, 97))

print("Binary search after sorting:", binary_search(sorted(scores), 97))

Output

Is 97 in the list? True
Binary search on the unsorted list: False
Binary search after sorting: True

Which search should you choose?

On sorted data, binary search is often much more efficient than linear search, and the bigger the list, the bigger the gap. "Often" matters: if the target happens to be the first element, linear search finds it in one check while binary search starts in the middle.

Choose linear search when the list is unsorted, is small, or is searched only once (sorting it first would cost more than the search saves). Choose binary search when the data is already sorted or will be searched many times, like a phone's contact list or a dictionary app.

Here is why "many times" changes the answer. Suppose a school app looks up student IDs in a list of 1,000 IDs, 500 times a day. Linear search averages about 500 checks for an ID that is in the list, so that is about 250,000 checks a day. Binary search needs at most 10 checks per lookup, so at most 5,000 checks a day, plus the one-time work of sorting the list. The bigger the list and the more lookups, the more the sorting pays for itself.

Check your understanding

A sorted list contains 200 numbers. What is the maximum number of elements binary search examines to find a value or decide it is not in the list?

A8B7C100D200

A program will use binary search on a list of numbers. Which of the following must be true about the list?

AThe list must be sorted.BThe list must have an odd number of elements.CThe list must not contain duplicate values.DThe list must contain the value being searched for.

Which of the following statements about searching are true? Select two answers.

Select 2 answers.

AOn a large sorted list, binary search usually examines far fewer elements than linear search.BLinear search can be used on a list that is not sorted.CBinary search examines fewer elements than linear search for every possible target.DLinear search works only when the list is sorted.

What value is returned by the call findFirst([4, 9, 2, 9, 5], 9)?

PROCEDURE findFirst(aList, target)
{
  index ← 1
  FOR EACH item IN aList
  {
    IF(item = target)
    {
      RETURN(index)
    }
    index ← index + 1
  }
  RETURN(-1)
}

A1B2C4D-1

Run this pseudocode

Binary search is used to look for 26 in the sorted list [3, 8, 12, 17, 21, 26, 30]. Which elements are examined, in order?

A17, 26B3, 8, 12, 17, 21, 26C17, 21, 26D21, 26

Binary search needs at most 10 checks to search a sorted list of 1,000 names. About how many checks would it need at most for a sorted list of 2,000 names?

A11B20C1,000D2,000

A coach keeps a list of player names in the order the players signed up and needs to check, once, whether a given name is on it. Which approach is guaranteed to give the correct answer?

ALinear search, because it works whether or not the list is sorted.BBinary search, because it is always faster than linear search.CBinary search, because the elements are names rather than numbers.DNeither search can be used until the list is sorted.

Linear search is used on an unsorted list of 500 numbers to look for a value that is not in the list. How many elements are examined?

A1B9C250D500

Practice exercises

Fix the Early Exit

Fix the Bug

This linear search should return True when target is anywhere in the list. But contains([4, 8, 15], 15) returns False. Find the bug and fix it.

def contains(items, target):

for item in items:

if item == target:

return True

else:

return False

Most Checks for Binary Search

Write Code

Write max_checks(n) that returns the maximum number of checks binary search needs on a sorted list of n elements.

Use the halving method: while n is greater than 0, count one check and replace n with n // 2 (the most elements that can be left after a check).

max_checks(7)     ->  3
max_checks(100)   ->  7

def max_checks(n):

# Count how many times you can halve n before it reaches 0

pass

Count the Binary Search Checks

Write Code

Write binary_search_checks(items, target) for a sorted list. It returns how many elements binary search examines before it finds target or runs out of elements. Follow these steps exactly:

Start with low = 0, high = len(items) - 1 and a count of 0.

While low <= high: set mid = (low + high) // 2 and add 1 to the count.

If items[mid] equals the target, return the count.

If the target is smaller than items[mid], set high = mid - 1; otherwise set low = mid + 1.

When the loop ends, return the count.

binary_search_checks([3, 8, 12, 17, 21, 26, 30], 17)  ->  1
binary_search_checks([3, 8, 12, 17, 21, 26, 30], 26)  ->  2

def binary_search_checks(items, target):

# Follow the steps in the instructions

pass

Exam topics: 3.10 Lists (AAP-2.O), 3.11 Binary Search (AAP-2.P)

What does it mean to traverse a list?

How does linear search work?

How does binary search work?

How do you trace binary search by hand?

How many iterations does binary search need?

Why must the data be sorted?

Which search should you choose?

Check your understanding

Practice exercises

Related Tutorials