Lists, Binary Search, and Procedures

Lists: Storing Many Values

A list is an ordered collection of items stored under one name. Instead of score1, score2, score3, … you write one list: scores ← [88, 92, 75]. This is data abstraction: one name stands for many values, so your program doesn't care how many there are.

Each item has an index, its position in the list. In AP pseudocode, the first item is at index 1. (Python starts at 0, so be careful when you switch.)

Here are the list operations from the AP reference sheet:

To visit every item, use FOR EACH:

total ← 0

FOR EACH x IN nums {

  total ← total + x

}

On each pass, x holds the next item, from first to last.

list ← [10, 20, 30]

INSERT(list, 2, 15)

REMOVE(list, 1)

Sequential and Binary Search

How do you find 26 in a list? The simplest way is sequential (linear) search: check item 1, then item 2, and so on until you find it or reach the end. It works on any list, sorted or not. But in the worst case it checks every item. For 1,000,000 items, that's 1,000,000 checks.

Binary search is much faster, but it has a requirement: the list must be sorted. The idea is the same as guessing a number from 1 to 100 when someone says "higher" or "lower."

1. Look at the middle item.

2. If it's your target, you're done.

3. If the target is smaller, throw away the middle and everything after it. If larger, throw away the middle and everything before it.

4. Repeat on the half that's left.

Each check cuts the remaining items in half.

How many checks does binary search need? About $\log_2 n$, the number of times you can halve $n$ before reaching 1. Since $2^{10} = 1{,}024$, searching 1,024 items takes at most about 10 checks. Doubling the list adds only one more check.

Procedures, Parameters, and Return Values

A procedure is a named block of code you can call whenever you need it. It can take parameters (inputs) and send back a result with RETURN.

PROCEDURE countAbove(list, limit) {

  count ← 0

  FOR EACH item IN list {

    IF (item > limit) {

      count ← count + 1

    }

  }

  RETURN(count)

}

• list and limit are the parameters: placeholders in the definition.

• When you call countAbove([72, 85, 90], 80), the values you pass in are the arguments.

• RETURN(count) ends the procedure and hands back a value. The call can be used like a value: DISPLAY(countAbove(scores, 80)).

This is procedural abstraction. You can use countAbove without thinking about how it counts, and if you fix a bug inside it, every place that calls it is fixed too. Write once, use many times.

PROCEDURE countAbove(list, limit)

{

  count ← 0

  FOR EACH item IN list

  {

    IF (item > limit)

    {

      count ← count + 1

    }

  }

  RETURN(count)

}

PROCEDURE mystery(a, b)

{

  IF (a > b)

  {

    RETURN(a)

  }

  ELSE

  {

    RETURN(b)

  }

}

Libraries and APIs

You don't have to write every procedure yourself. A library is a collection of ready-made procedures that other programmers wrote. An API (application programming interface) describes how to call those procedures: their names, the parameters they expect, and what they return. For example, a weather API might give you a procedure getTemperature(city) that returns a number. You only need the documentation to use it, not the code inside. That is procedural abstraction again.

When you use someone else's library, give attribution: credit the author and follow the license.

Putting It Together: Edge Cases

Lists and procedures work together. Here is a procedure that finds an average:

PROCEDURE average(list) {

  total ← 0

  FOR EACH x IN list { total ← total + x }

  RETURN(total / LENGTH(list))

}

For [80, 90], total is 170 and it returns 170 / 2 = 85. But what about an empty list? Then LENGTH(list) is 0 and the program divides by zero, which is an error. Always test edge cases: empty lists, one item, the first or last index.

A fix uses selection:

IF (LENGTH(list) = 0) { RETURN(0) }

placed at the start of the procedure.

Back to the start: the music app can find a song among 1,000,000 in about 20 checks because the song list is sorted and binary search halves it every time ($2^{20} \approx 1{,}000{,}000$).

PROCEDURE average(list)

{

  total ← 0

  FOR EACH x IN list

  {

    total ← total + x

  }

  RETURN(total / LENGTH(list))

}

Summary