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.
cd ~/DCS127In 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:
// please just leave the comments about logic
// 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.
run Linear.javaThis 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 sortedto 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).
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.javaor
enscript -Pitlevel1 Linear.javaShow 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.
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.
size *50 nanosecondsto 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:i→array[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[3] to array[13] 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[3] is never considered!
This is www.PaulTaylor.EU/algorithms/linear.html and it was derived from algorithms/linear.tex which was last modified on 21 July 2007.