//------------------------------------------------------
// File: binSearch.cpp
// Name: Sharon Tuttle
// last modified: 2-3-05
//
// Contract: binSearch : int[] int int int -> int
//
// Purpose: See if val is contained within ordered array
//          valArr within the range of indices 
//          [leftIndex, rightIndex]; return the index
//          where found if so, and -1 if not.
//
// preconditions: 
//    *   the elements within valArr are in ascending order; 
//    *   there are no duplicate values in valArr;
//    *   leftIndex is in the range [0, size of valArr];
//    *   rightIndex is in the range [0, size of valArr];
//
// postconditions:
//    *   returns -1 if val is not in the range [leftIndex, rightIndex]
//    *   returns i if valArr[i] == val
//
// Examples: if int arr1[] == {1, 3, 8, 27, 56, 77, 78, 79, 100}:
//         binSearch(arr1, 0, 8, 50) == -1
//         binSearch(arr1, 0, 8, 150) == -1
//         binSearch(arr1, 0, 8, 0) == -1
//         binSearch(arr1, 0, 8, 1) == 0
//         binSearch(arr1, 0, 8, 100) == 8
//         binSearch(arr1, 0, 8, 56) == 4
//
//         if int arr2[] == {}:
//         binSearch(arr2, 0, 0, 13) == -1 
//---------------------------------------------------------------------

#include <iostream>
#include <cmath>
#include <cassert>
using namespace std;

int binSearch(int valArr[], int leftIndex, int rightIndex, int val)
{
    // uncomment cout below to "play" with seeing what arguments this
    //    is called with;
    //
    //cout << "called binSearch with leftIndex: " << leftIndex 
    //     << " and rightIndex: " << rightIndex << endl;

    int midIndex;   // index of the middle element in this range

    // which preconditions can we reasonably test with assert 
    //    statements before beginning? 
    assert(leftIndex >= 0);
    assert(rightIndex >= 0);
    
    // base case #1 --- is there anything to search?
    if (rightIndex < leftIndex)
    {
        // element was NOT found --- return -1, failure
        return -1;
    }

    // base case #2 --- there is only ONE element to search
    else if (rightIndex == leftIndex)
    {
        if (valArr[leftIndex] == val)
        {
            // element FOUND! return its index
            return leftIndex;
        }
        else
        {
            // element NOT in array --- return -1, failure
            return -1;
        }
    }

    // if get here --- there's still more to search;
    else
    {
        // look at element in MIDDLE of this range;
        midIndex = static_cast<int>(ceil( 
             leftIndex + 
             (static_cast<double>
                 (rightIndex - leftIndex)/2)
                       ));

        // base case #3 --- element IS in the middle;
        if (valArr[midIndex] == val)
        {
            return midIndex;
        }
     
        // element is NOT in the middle...

        else
        {
            // recursive case #1: val is LESS THAN 
            //    middle value;
            //    continue looking in LEFT of range;
            if (val < valArr[midIndex])
            {
                return binSearch(valArr, 
                                 leftIndex, midIndex-1, 
                                 val);
            }
            
            // recursive case #2: val is MORE THAN 
            //    middle value;
            //    continue looking in RIGHT of range;
            else
            {
                return binSearch(valArr, 
                                 midIndex+1, rightIndex,
                                 val);
            }
        }
    }
}