// Introduction to Algorithms
// Four versions of Binary Search, plus variations
// <put your name, login name & student number here>

// please dont change anything above the line
public class Binary implements Searching {

    // "run Binary.java choice=3" sets this,
    // and thereby controls which version you get
    public static int choice = 0;
    public void choice (int c) {
	choice=c;
    }
    public boolean sorted_data () { return true; }
    public int search (int[] array, int seek) {
      int size = array.length;
      boolean trace = Trace.trace;
    switch (choice) {
      
    default:

	// ====================================================
	// I recommend that you don't alter cases 1-4 
	// they are all correct
	// (leave them for reference and copying)

    case 1: { // caled "A" in the lecture
	int bot = -1;
	int top = size;
	while (top - bot > 1) {
	    int mid = (top + bot)/2;
	    if (trace) Trace.printarray (array, bot, mid, top);
	    if     (array[mid] <  seek) bot = mid;
	    else /* array[mid] >= seek */ top = mid;
	}
	if (trace) Trace.printarray (array, bot, top);
	return top; }

    case 2: { // "B"
	int bot = 0;
	int top = size;
	while (top > bot) {
	    int mid = (top + bot - 1)/2;
	    if     (array[mid] <  seek)   bot = mid + 1;
	    else /* array[mid] >= seek */ top = mid;
	}
	return top; }
      
    case 3: { // "C"
	int bot = 0;
	int top = size - 1;
	while (top >= bot) {
	    int mid = (top + bot)/2;
	    if      (array[mid] <  seek)    bot = mid + 1;
	    else /* (array[mid] >= seek) */ top = mid - 1;
	}
	return bot; }

    case 4: { // "D"
	int bot = -1;
	int top = size - 1;
	while (top > bot)
	    { int mid = (top + bot + 1)/2;
	    if     (array[mid] <  seek)   bot = mid;
	    else /* array[mid] >= seek */ top = mid - 1;
	    }
	return top+1; }

    // ====================================================
    // Cases 11-14 are identical to cases 1-4 
    // make your alterations to these

    case 11: { // caled "A" in the lecture
	int bot = -1;
	int top = size;
	while (top - bot > 1) {
	    int mid = (top + bot)/2;
	    if (trace) Trace.printarray (array, bot, mid, top);
	    if     (array[mid] <  seek) bot = mid;
	    else /* array[mid] >= seek */ top = mid;
	}
	if (trace) Trace.printarray (array, bot, top);
	return top; }

    case 12: { // "B"
	int bot = 0;
	int top = size;
	while (top > bot) {
	    int mid = (top + bot - 1)/2;
	    if     (array[mid] <  seek)   bot = mid + 1;
	    else /* array[mid] >= seek */ top = mid;
	}
	return top; }
      
    case 13: { // "C"
	int bot = 0;
	int top = size - 1;
	while (top >= bot) {
	    int mid = (top + bot)/2;
	    if      (array[mid] <  seek)    bot = mid + 1;
	    else /* (array[mid] >= seek) */ top = mid - 1;
	}
	return bot; }

    case 14: { // "D"
	int bot = -1;
	int top = size - 1;
	while (top > bot)
	    { int mid = (top + bot + 1)/2;
	    if     (array[mid] <  seek)   bot = mid;
	    else /* array[mid] >= seek */ top = mid - 1;
	    }
	return top+1; }
    // ====================================================
    }
  }
}

/* ======================================================================

Use "check" to verify that cases 1-4 are correct.

Paste in the correctness reports of the tester
- do they return the leftmost, rightmost or just any occurrence of "seek"?
- when "seek" is absent, should it be inserted before or after the
position returned?

There is a slight difference in the amount of time that they take.
Find out the coefficient of "n log(n)" and paste it in.  Which is faster?

These algorithms ONLY work when the array satisfies a certain PRECONDITION.
- What is this condition?
- What happens if it is not satisfied?
- How does this compare with the effect of failing the precondition
  for the "shift" exercise?
- In that exercise, the Tester insisted that you should check the
  precondition before proceeding with the shift, and throw an Exception
  if it fails.   Should you do the same with Binary search?

We shall say that the algorithm "makes an early exit" (and rename it
AX, BX, CX or DX) if it has the additional test
	    if     (array[mid] == seek)   return mid;

Make a copy of cases 1-4 and insert this line.  If you want to do just
one of the four, do case 3 ("CX"), as this popularly occurs in textbooks.

What difference does this make to the correctness report (leftmost etc)?

What difference does this make to the time?

Make another copy (of all four this time), without the "early exit",
but changing "<" to "<=".

What difference does this make to the correctness report (leftmost etc)?

Change the initialisations from 0 to -1 (or vice versa) and from size
to size-1 (or vice versa).   What exactly goes wrong?

Change the loop condition (while (top > bot) etc).
- What happens if you make the condition stronger (eg while (top > bot+1)),
  so the loop exits earlier?
- What happens if you make it weaker, so it exits later?

Change the calculation of mid = (top + bot + 1)/2 etc.  Keeping your
alternative version of mid, make some other change that puts right the
damage that it causes.  What is wrong now?  Can you fix it with extra code?
(Hint: look at the "D" versions in last year's binary search exercises.)

Look inside the file Binary.plot to find out how to plot time against 
the logarithm of the size, so 2, 4, 8, 16, 32, 64, ... are equally spaced.

If you are VERY careful with the experiments, you can find out the size
of the primary memory cache within your CPU, and how long it takes to
fetch data from the secondary cache within the CPU.

 ====================================================================== */