1. arrays have a regular structure

   1. an value followed by an array

   2. an array followed by a value

   3. a value between two arrays

   4. in general, a single value and smaller arrays

      1. note the smaller arrays have the same structure

2. array algorithms can have a structure similar to arrays

   1. an algorithm is a recipe for performing a calculation

   2. do_something(a[1..n])
        if do_something(a[1]) is o.k. return
        do_something(a[2..n])
      

   3. do_something(a[1..n])
        do_something(a[2..n])
        if do_something(a[1]) is o.k. return
      

   4. array pictures are helpful in understanding these algorithms

3. example - linear search

   1. the problem - given an array a and a value x, return the index of x in a or -1 if x doesn't appear in a.

   2. which algorithm form to use

      1. the value doesn't interact with the array - use the first form.

   3. int find(a[1..n], x)
        if a[1] == x return i
        if 1 == n return -1
        return find(a[2..n], x)
      

   4. what's the array picture?

4. example - star strings

   1. problem - return the leftmost index of the longest sequence if stars in a string

   2. which algorithm form to use

      1. the value does interact with the array, use the second form

   3. int star_string(a[1..n])
        i = star_string(a[1..n - 1])
        if a[1..n] forms a new longer star string
          set i properly
        return i
      

   4. what's the array picture?

This page last modified on 21 June 2001.