// Code Kata 2: http://blogs.pragprog.com/cgi-bin/pragdave.cgi/Practices/Kata/KataTwo.rdoc
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;


const int SIZE = 255;


// Day 1: Iterative chopping
int iterativeChop(int num, int v[]) {
  int start = 0,
      end = SIZE - 1,
      pos;

  while(true) {
    pos = (end + start) / 2;

    if(start == end - 1) 
      return -1;

    if(v[pos] == num) {
      return pos;
    }
    else {
      if(num > v[pos]) 
        start = pos;
      else 
        end = pos;
    }
  }
}


// Day 2: Recursive chopping
int recursiveChop(int num, int v[], int start = 0, int end = SIZE) {
  int pos = (end + start) / 2;

  if(start == end - 1) { 
    cout << "about to return -1 from recursiveChop()" << endl;
    return -1;
  }

  if(v[pos] == num) {
    cout << "about to return " << pos << " from recursiveChop()" << endl;
    return pos;
  }
  else {
    if(num > v[pos]) 
      recursiveChop(num, v, pos, end);
    else 
      recursiveChop(num, v, start, pos);
  }
}


int main() {
  int v[SIZE],
      r;

  srand(time(0));
  r = (rand() % (SIZE * 2)) + 1;

  for(int i = 0; i < SIZE; i++)
    v[i] = i * 2;

  cout << "iterativeChop(): Index of " << r << " is " << iterativeChop(r, v) << endl;
  cout << "recursiveChop(): Index of " << r << " is " << recursiveChop(r, v) << endl;

  return 0;
}