//*****************************************************************
// R. A. Hillyard
// binSearch.cpp
// 
// Program to illustrate implementation of the binary search algorithm
// on a sorted list.
//*****************************************************************
#include <iostream>

using namespace std;

int listSize = 15;
int binSearch(char l[], int size, char key, int &count);

int main()
  {
  int index;
  int count;
  char list[] = {'a','b','c','g','h','l','n','p','q','r','s','u','w','x','z'};

  index = binSearch(list, listSize, 'a', count);
  if(index != -1)
    {
    cout << "found a at index: "  << index <<" after "<<count<<" tries" << endl;
    }
  else
    cout << "did not find a" <<" after "<<count<<" tries"<< endl;

  index = binSearch(list, listSize, 'o', count);
  if(index != -1)
    {
    cout << "found o at index: "  << index <<" after "<<count<<" tries" << endl;
    }
  else
    cout << "did not find o" <<" after "<<count<<" tries"<< endl;

  index = binSearch(list, listSize, 'p', count);

  if(index != -1)
    {
    cout << "found p at index: "  << index <<" after "<<count<<" tries" << endl;
    }
  else
    cout << "did not find p" <<" after "<<count<<" tries"<< endl;
  }

//*****************************************************************
int binSearch(char l[], int size, char key, int &count)
  {
  int first = 0;      //first element of the array
  int last = size-1;  //last element of the array
  int mid;
  count = 0;

  while(last >= first)
    {
    count++;
    mid = (first+last)/2;    //pick the middle of the list - round down
    if(l[mid] == key)        //if key is in middle - return it
      return mid;
      
    else if(key < l[mid])    //search upper half of list
      last = mid-1;
      
    else
      first = mid+1;         //search lower half of list
    }//end while
  return -1;
  }//end binSearch
//*****************************************************************
/******************Program output********************/
found a at index: 0 after 4 tries
did not find o after 4 tries
found p at index: 7 after 1 tries