#include <iostream>
#include <cmath>
#include <cassert>
#include "count_seql.h"
using namespace std;

int count_combo(int valArr[], int leftIndex, int rightIndex, int val, int& comps_so_far)
{
    int midIndex;   // index of the middle element in this range
    const int SMALL_ENOUGH = 20;

    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)
    {
        // in either case, make 1 comparison below to see if element is here
        comps_so_far++;

        if (valArr[leftIndex] == val)
        {
            // element FOUND! return its index
            return leftIndex;
        }
        else
        {
            // element NOT in array --- return -1, failure
            return -1;
        }
    }

    else if ( ((rightIndex - leftIndex)+1) <= SMALL_ENOUGH)
    {
        return count_seql(valArr, leftIndex, rightIndex, val, comps_so_far);
    }
 
    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)
        {
            // this comparison was made...
            comps_so_far++;
            return midIndex;
        }
     
        // element is NOT in the middle...

        else
        {
            // above if comparison failed, and am making 1 comparison
            //    below...
            comps_so_far += 2;

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