// Introduction to Algorithms
// Linear search from the right
// <put your name, login name & student number here>

// This file is essentially identical to "Linear.java".
// You might prefer to copy your own version of that,
// instead of using this new clean one.

// In "Linear.java" you should have written a method that
// searches an array from the LEFT, starting at position 0.
// Write similar code in this file that searches from the
// RIGHT (position size-1) instead, and re-answer the questions.

public class RLinear implements Searching {

    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; }
}

/************************************************************************

Now answer the following questions IN THIS FILE:

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?

<insert your answer here>

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?

<insert your answer here>

Why is this an APPROPRIATE result for the method to return in this case?

<insert your answer here>

Now do this:
	check Linear.java

<insert what the Tester reports here>

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.

Exercise 1(c) is in the file "ILinear.java".

***********************************************************************/