/COMPUTER SCIENCE 161.01
//WEDNESDAY NOV 14TH 2018

//BINARY SEARCH

//THE PROGRAM BELOW PERFORMS THE BINARY SEARCH ALGORITHM
//IT IS MUCH MORE EFFICIENT THAN SEQUENTIAL SEARCH
//BUT IT REQUIRES THAT THE lastNames ARRAY BE IN ALPHABETICAL ORDER
	//HERE, N is 15.

lastNames = new Array("Arrington", "Atkinson", "Branch", "Burleson",
                      "Clagett", "Davis", "Gilliam", "Haiss",
                      "Hiter", "McVey", "Molali", "Morgan", 
                      "Sydney", "Valente", "Wilkins");

firstNames  = new Array("Ben", "Wes", "Zach", "Alex",
                        "Bobby", "Michael", "Hunter", "David",
                        "Ben", "Robert", "Will", "Chris",
                        "Algernon", "Tom", "Austin");

N = lastNames.length;
desired = prompt("Enter last name of desired person: ");

first = 0;  
last = N-1;
found = false;

count = 0;  //to count loop iterations

while (first <= last && found == false) {

      mid = (first + last)/2;     

      alert("first = " + first + "  last = " + last + "  mid = " + mid);

      if (desired > lastNames[mid])
           first = mid + 1;
      else if (desired < lastNames[mid])
           last = mid - 1;
      else
           found = true; 

      count++;
}

if (found == true)
  alert("Happy Wednesday to " + firstNames[mid]);
else {
  alert("first = " + first + "  last = " + last);
  alert("Could not find " + desired);
}

 
//REPORT AT BOTTOM… 

count + " comparisons"