#include <stdio.h>
#include <assert.h>

int recursive_find(int sorted_array[], int start, int end, int value) {
	if (start > end) {
		return -1;
	}

	if (start == end && value == sorted_array[start]) {
		return start;
	}

	int index = (start + end) / 2;
	if (value == sorted_array[index]) {
		return index;
	}

	if (value > sorted_array[index]) {
		return recursive_find(sorted_array, index + 1, end, value);
	} else {
		return recursive_find(sorted_array, start, index - 1, value);
	}
}


int binary_find(int sorted_array[], int length, int value)
{
    if (0 == sorted_array || length <= 0)
    {
        return -1;
    }            

    return recursive_find(sorted_array, 0, length - 1, value);
}

int recursive_findex(int circlesorted_array[], int start, int end, int value)
{
    if (start > end)
    {
        return -1;
    }

    if (value == circlesorted_array[start])
    {
        return start;
    }

    if (value == circlesorted_array[end])
    {
        return end;
    }

    if (start == end && value == circlesorted_array[start])
    {
        return start;
    }

    int head = circlesorted_array[start];
    int tail = circlesorted_array[end];

    if (head < tail)
    {
        return recursive_find(circlesorted_array, start, end, value);
    }

    int index = (start + end) / 2;
    int index_data = circlesorted_array[index];
    
	if (value == index_data)
    {
        return index;
    }
    
    if (index_data < tail)
    {
        if (value > index_data && value < tail)
        {
            return recursive_find(circlesorted_array, index + 1, end, value);
        }
        else
        {
            return recursive_findex(circlesorted_array, start, index - 1, value);
        }
    }
    else if (index_data > tail)
    {
        if (value < index_data && value > head)
        {
            return recursive_find(circlesorted_array, start, index - 1, value);
        }
        else
        {
            // return recursive_find(circlesorted_array, index + 1, end, value);
	    // not recursive_find, should be recursive_findex			
             return recursive_findex(circlesorted_array, index + 1, end, value);
        }
    }
    else
    {
        return -1;
    }
}

int binary_findex(int circlesorted_array[], int length, int value)
{
    if (0 == circlesorted_array || length <= 0)
    {
        return -1;
    }

    int head = circlesorted_array[0];
    int tail = circlesorted_array[length - 1];
    if (head < tail)
    {
        return binary_find(circlesorted_array, length, value);
    }
    else
    {
        return recursive_findex(circlesorted_array, 0, length - 1, value);
    }
}

void demo() {

	int sorted_array[] = {-1, 2, 5, 8, 11, 12, 13, 15, 49, 236, 1231, 9836};
	int result = binary_find(sorted_array, sizeof(sorted_array) / sizeof(int), 4);
	assert(result == -1);
	printf("the result is: %d\n", result);
	result = binary_find(sorted_array, sizeof(sorted_array) / sizeof(int), 2);
	assert(result == 1);
	printf("the result is: %d\n", result);

	int circlesorted_array[] = {15, 49, 236, 1231, 9836, -1, 2, 5, 8, 11, 12, 13};
	result = binary_findex(circlesorted_array, sizeof(circlesorted_array) / sizeof(int), 4);
	assert(result == -1);
	printf("the result is: %d\n", result);
	result = binary_findex(circlesorted_array, sizeof(circlesorted_array) / sizeof(int), 8);
	assert(result == 8);
	printf("the result is: %d\n", result);
}

#include <vector>
#include <iostream>
#include <algorithm>

template<typename T>
int b_find(T& xs, int v){
  if(xs.empty())
    return -1000;

  if(xs.size()==1)
    return xs[0]==v? 0: -1000;
  
  int offset=xs.size()/2;
  if(v==xs[offset])
    return offset;

  T left(xs.begin(), xs.begin()+offset);
  T right(xs.begin()+offset, xs.end());

  int i;
  if(xs.front()<xs[offset] && xs[offset]>xs.back())
    if(v>xs[offset])
      return b_find(left,v);
    else if((i=b_find(left, v))>0)
      return i;
    else
      return left.size()+b_find(right,v);
  else //xs.front()>xs[offset] && xs[offset]<xs.back()
    if(v<xs[offset])
      return b_find(left, v);
    else if((i=b_find(right, v))>0)
      return i+left.size();
    else
      return b_find(left,v);
}

template<typename T>
int binary_find(T& xs, int v){
  int res=b_find(xs, v);
  return res<0? -1: res;
}

int main(int, char**){
  const int xs[]={20, 24, 6, 7, 9, 11, 13};
  std::vector<int> xsv(xs, xs+sizeof(xs)/sizeof(int));
  std::cout<<binary_find(xsv, 6)<<"\n";
  std::cout<<binary_find(xsv, 15)<<"\n";
}