#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);
}