# Introduction to Algorithms: Linear Search

### 15 January 2001

The first exercise is to find (an occurrence of) a value in an array on integers by examining each cell from one end of the array to the other.
You need to write fewer than six lines of JAVA.

## 1  Setting up your work for this course

There are two very important differences between the exercises for Programming I and those for this one. This is not "just another programming course".
• This course is about components: you only write the method that does the specific job in hand, in this case searching an array. It is not about whole programs, so you will never be writing
```    public static void main (String[] args)
```
as the main method is provided by the TESTER program that I have written for this course. Nor will you be allowed to write
```    System.out.print (message);
```
because the TESTER will call your method millions of times (to check that it's correct in different cases and to time it). Instead you can write
```    Trace.print (message);
```
which will only print the message if you invoke the TESTER with the trace command, and not if you invoke it with the run or check commands.
• This course is about specification of problems and the behaviour of algorithms to solve the problems. Much of your time will be spent on experiments to find out how the different algorithms work and how fast they are. This course is as much a continuation of Introduction to Logic as it is of Programming I: it is the application of logical techniques to programming. You will be using logic to describe precisely what the algorithms do.
As in Programming I, you are to use the Linux operating system for this course, and run your programs from a "command line" and not from a GUI (graphical user interface). You will need just two windows on your screen:
• an editor, for which I strongly recommend xemacs, and
• a terminal window (shell, xterm).
Begin by making these as large as possible, to make good use of the space on your screen. The TESTER will generate quite a lot of lines of output, and you will want to see as much of this and of your program as you can fit on the screen.
You do not need Netscape. Later you will be doing experiments to find out how long your code takes to run. Netscape is an enormous and bug-ridden program that is very wasteful of system resources; if it is active on your workstation, it will interfere with these experiments, and the results of these experiments will be inferior.

## 2  Writing the JAVA code

In your personal filespace you will find that a directory called DCS127 has recently been created for you. All of your work for this course must be done in this directory. Do
```    cd ~/DCS127
```
In the directory is a file called Linear.java. This is a template in which you will fill in the code for the search method.
It already contains the following:
```   // DO NOT CHANGE the "class" line
public class Linear implements Searching {
// Here is the one method that you have to write.
// Do not change the method declaration
// (yes, it must be "public" and NOT "static").
public int search (int[] array, int seek) {
int size = array.length;
// A logical formula
// (the "precondition" of the method)
// belongs here.
// This will be discussed in the next lecture:
// here as they are,   and add the logical
// formulae during or after the lecture.
// You ONLY need to declare this one local variable.
int position;
// Another logical formula
// (the "precondition" of the loop)
// belongs here.
// Please use "while", NOT "for", in this course.
// (The thing that you write in brackets
// will be called the "loop test" in this course.)
while (     ) {
// Yet another logical formula
// (the "loop invariant")
// belongs here.
// Write your code (the "body" of the loop) here.
}
// The fourth and final logical formula
// (the "postcondition" of the loop and of the method)
// belongs here.
// Here we say where "seek" occurs in the array
// and go home.
return position;
}
// PLEASE IGNORE THESE LINES - DO NOT CHANGE THEM
public static int choice = 0;
public void choice (int c) { choice=c; }
public boolean sorted_data () { return false; }
}
```
Note: "seek" is an irregular verb: I seek, I sought (past tense), I have sought (past participle), the value is sought (passive participle).
Be careful to distinguish between pointers or indices into the array and the values that are contained in it.

## 3  Running your program

When you have written your code, in the terminal window do
```    run Linear.java
```
This will compile your code for you (do not use javac) and run it on a random array of length 20.
Do this several times.
You can make the TESTER call your method with a longer or shorter array, or one that is sorted (ascending), reverse sorted (descending) or strictly sorted by addition combinations of words like
```    run Linear.java size=10 strictly reverse sorted
```
to the command.
Alternatively, you can tell it exactly what array to use:
```    run Linear.java array=2,4,6,8,0,9,7,5,3,1 seek=5
```
(beware that there must be no spaces in the list of numbers).

## 4  The experiments

Now answer the following questions in your JAVA source file (Linear.java). The source files for each algorithm will then contain everything that you learn about that algorithm, and will form the basis of your exam revision notes.
In the situation where seek occurs twice or more often in the array, which position of the two or more occurrences does your method indicate?
What position does your method return if seek is not in the array? In what way does this number depend on the size of the array?
Why is this an appropriate result for the method to return in this case?
What other result value might you choose to return in this case instead? Give a reason.
How would you change the code to make it return this alternative result? (Insert your changed code following this question in Linear.java - do not change what you have written towards the beginning of the file.)
Now do this:
```    check Linear.java
```
"Cut and paste" what the TESTER reports at the place indicated in Linear.java.
Does the TESTER confirm what you observed about the cases where seek is either absent or occurs more than once in the array?
Assuming that you have written your code in the very simple way that was intended, you should find that its behaviour can be described more precisely than what you were originally asked to do, or expected yourself than it would do. In what way is it more precise?
When your code is correct and you have finished your answers to these questions, print out this file (including your answers) by doing
```    a2ps -Pitlevel1 Linear.java
```
or
```    enscript -Pitlevel1 Linear.java
```
Show your printout to the teaching assistant, and bring it to the next lecture, so that you can write in the logical formulae mentioned above.
Then look at the file RLinear.java. It is essentially identical to Linear.java, but you are asked to do write code to do something slightly different, and then answer the same questions about it.

## 5  Searching to insert

The first few exercises lead up to the implementation of insertion sort. The idea of this algorithm is to insert successive values into the segment of the array that has been sorted so far, by searching for the appropriate position and shifting the intervening stuff.
The specification for search to insert is more complicated than that for the linear search that you did last week. It has to meet the requirements of the application that will use it (insertion sort). These are different in two ways:
• you have to say where to insert the value (seek), rather than where it already occurs - which it probably won't;
• you are only looking in part of the array, namely upto the end of the so-far sorted segment.
What you have to provide is therefore slightly more difficult, but what you are given is also more generous: this segment of the array is already sorted.
The file ILinear.java is in your coursework directory.
The template is
```   class ILinear implements SearchingToInsert {
public int where_to_insert (int[] array, int upto, int seek) {
}
public void choice(int c) {}
}
```
which is similar to linear search, apart from the extra argument upto.
When linear search failed to find seek in random data, it could do nothing more informative than return -1 or size.
However, when the array is sorted, it can say where_to_insert the new value to keep the array sorted.
If position is the place before which to make the insertion, what inequalities hold amongst seek and the values in the array?
Write the code and use the TESTER to try it out as you did for the striaghtforward linear search.

## 6  Correctness and complexity

This was part of the model answer for the first test in 2000; the rest of the test was about binary search.
Linear search takes typically
size *50 nanoseconds
to execute. The time depends linearly on the length of the array, but you should also be aware that it takes a fraction of a microsecond to go round the loop once.
Also, if there are not very many different values occurring in the array (for example, if they are integers that are significantly smaller than the length of the array), then the first occurrence of a particular value will be found sooner.
This code returns the position of the first or leftmost occurrence of seek. The array does not have to satisfy any special requirement for the method to conform to this specification.
More generally, if we regard the array as a function, f:iarray[i], the search for a particular value x is trying to calculate the inverse of the function, f−1(x). This inverse value is a set, which may be empty, a singleton or have more than one element. However, search is specified to return, not a set, but an int, which, moreover, must be an element of the set f−1(x) if this set is non-empty. It is not, therefore, able to tell us everything there is to say about the set f−1(x).
Treating it as an inverse function is therefore not the appropriate way of making the specification of search more precise. Instead, we consider the way in which it may be used, for example as a subroutine in insertion sort.
In the case where f−1(x)=∅, i.e. the value sought does not occur anywhere in the array, a user such as insertion sort would be interested in the position before (or after) which to insert the value. This requirement only makes sense if the array is sorted.
By changing the code to
```   int position = 3; while (position < 14)
```
it will search the segment array to array inclusive, instead of the whole of the array.
Note that while (pos >= 3 && pos <= 13) does not work: following the initialisation pos=0, the loop condition fails immediately, so array is never considered!

(To be written.)

## 8  Searching for the minimum

(To be written; this is for selection sort. There could be more exercises on other similar linear algorithms.)

This is www.PaulTaylor.EU/algorithms/linear.html and it was derived from algorithms/linear.tex which was last modified on 21 July 2007.