G12FCO -- Formal Computation

Lecture 2 -- Searching

In this lecture, we look at the construction of a particular algorithm for a common problem, from the point of view of the properties of algorithms discussed last time. Specifically, we look at the problem of searching. We have a collection of things, say people. We also have a given property of some particular thing, say the name of someone. We have to search the collection to try to find a thing that has that property (someone who has that name). This is still too general a concept for a simple computer program, so let us consider the following more computerised problem:

Problem: There is given an array a, with subscripts that run from 1 to N, where N is also given. The array contains integers. Finally there is also given an integer j. We are required to set an integer i to the value of a subscript, between 1 and N, such that a[i] = j, or, if no such subscript exists, to zero.

We can think of this as potentially a subroutine or function that should return i, with zero representing failure. We use integers rather than names simply because every computer language handles integers in much the same way -- definitely not true of names! In a real application, there would be other information that was held in parallel with the information in a, such as address, age, sex, income, ..., and the returned value of i would be used, if valid, to access this parallel information. In many languages, a data structure facility is provided to allow such parallel information to be accessed conveniently; for example, to allow us to define a person to be a structure comprising a name, an address, an age, a sex, an occupation, an eyecolour, and so on.

Searching an unsorted array

On the information given so far, there is really not much choice about how to solve this problem. The desired element of the array could be anywhere; we can't show it's not there except by looking at every element. There's no point in doing anything other than starting at one end and looking along until we get to the other, stopping only if we find what we're looking for. Thus:

		i = N
		while i > 0
		   if a[i] = j then exitwhile else i = i-1
		endwhile

[This is an approximation to QBasic; converting it to real QBasic or to C -- where it is extremely compact -- or to Pascal or whatever is left to the reader.] It's convenient to start at the top and work down simply because this will, more-or-less accidentally, set i to zero if j isn't found, at no extra cost.

Note: A common requirement is that if j is not found, then it is to be added to the collection, at position N+1, and N incremented to match. This can be done using a sentinel; j is added anyway, without changing N, you search up the array, but because the sentinel is there you know that you will eventually find j, so you don't need to test for running off the end of the array. If you find only the sentinel, then you update N. This can be a neat trick, but it has its dangers too -- the array may fill up one element too soon, there are problems if your computer uses parallel processing [don't ask!], and it's less efficient if searches are usually successful.

For many search problems, this solution is simply too slow. [Imagine trying to use a telephone directory in which the names are in random order!] To search faster, the information must be sorted.

Searching a sorted array

So, let us assume from now on that the array a has been sorted, so that a[1] is the smallest element, a[2] the next smallest, and so on, up to a[N] the largest. The difference this makes is that if we look at a typical element, we find whether it is bigger or smaller than j, and this enables us to eliminate whole swathes of the array. [If you are looking up `Walker' in the telephone directory, and you open the book at `Smith', then you don't need to search pages before that, and you quickly home in on the right page.]

In computer terms, this is usually implemented by [so-called] binary chop. In other words, we keep two fingers, let us call them lo and hi, on the array, initially set to the first and last elements, respectively, which mark the part of the array within which the search can be confined. We then look at the middle element between lo and hi. If this is too low, we can move up our lo finger, if too high, we can move down our hi finger, and keep going until either we find j or the fingers meet.

It makes a good programming exercise to write code that implements this. Please try it now. Don't worry about the language used or the coding details; concentrate on making sure that lo, hi and the other variables get set to the correct values, and that your code gives the correct value of i in all cases.

Pause ....

Stop! Please do not read the rest of these notes until after you have actually tried to do this [e.g. in the lecture!].

Here are some special cases for you to try;

N is a power of two
N is odd
N = 1
N = 0
j is exactly the middle element of the array
j is less than the smallest element of the array
j is greater than the biggest element of the array
j is between two elements of the array
combinations of the above

Almost all first attempts fall foul of at least one special case! And yet, if you look at it the right way, this program is easy to get right. How?

Start with an invariant. We want to say that there is some interval of the array within which j must be found, if it is present. This interval will be from lo to hi inclusive, guaranteed initially by setting lo = 1 and hi = N. We try to reduce the interval while maintaining this guarantee.

Eventually, one of two things will happen: either the interval becomes empty, in which case j cannot be present; or we find j. When is the interval empty? When lo > hi. [If they are equal, there is still just one element left to search.] So the guts of the code will be while lo <= hi ....

How do we reduce the interval? By looking at an element in it; if this element is equal to j, we've found it, if it's less than j we can advance lo to the next element past it, and if it's greater than j we can reduce hi to the previous element. Which element? Any between lo and hi [inclusive] will do, but it makes sense to use the middle element, (lo+hi)/2.

With that preparation, please try to write the code again.

Pause ....

Stop again! Please do not read the rest of these notes until after you have actually tried to do this [e.g. in the lecture!].

You should have something rather like:

	lo = 1; hi = N
	while lo <= hi
	   do mid = (lo + hi) / 2
	      if a[mid] = j
		then i = mid; exitwhile
		else if a[mid] < j
		then lo = mid + 1
		else hi = mid - 1
	      endif
	endwhile
	if lo > hi then i = 0

Again, converting this to genuine QBasic or to C or to Pascal is easy and is not the point of the exercise. Is this a good algorithm? Let's see.

It is deterministic; we've given the program for it.
It terminates. Every time into the loop, either we exit, or we go round again with either lo increased or hi decreased; since lo and hi are integers, eventually the condition lo <= hi must fail.
It is correct. The invariant shows that if lo > hi, then j cannot be found, and i is then correctly set to zero, and the only other way out is if j was found and then i is set to mid, the element where it was found. [We could actually replace mid by i throughout, which would slightly simplify the code, but would make this proof of correctness rather more obscure.]

top of page

G12FCO home page. border=0

Previous lecture. border=0

Next lecture. border=0

Problem Class 1 .