/* Include lib */
#include <stdio.h>

/* Define */
#define ARRAY_MAX               8
#define ROTATED_SORTED_ARRAY    { 0, 1, 2, 3, 4, 5, 6, 7 }
#define PIVOT_INDEX             3
#define SEARCH_VAL              0

int rotated_array[ARRAY_MAX] = ROTATED_SORTED_ARRAY;

/* API */
/* API binary search with sorted array */
int binary_search(int *arr, int size, int key)
{
   int start, end, mid;
   
    if (!arr) {
        printf("Wrong input !!\n");
        return -2;
    }

    if (size == 0) {
        printf("Wrong size !!\n");
        return -2;
    }

    start = 0;
    end = size - 1;
    while (start <= end) {
        mid = (start + end) / 2;
       
        if (arr[mid] == key)
            return mid;
        
        if (key < arr[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
   }
   
   return -1;
}

/* API search rorated array */
int search_rotated_array(int *arr, int size, int pivot, int key)
{
    int new_arr[ARRAY_MAX] = { 0 };
    int i, ret;

    if (!arr) {
        printf("Wrong input !!\n");
        return -2;
    }

    if (size == 0 || pivot >= size) {
        printf("Wrong size or pivot !!\n");
        return -2;
    }

    /* Get new array from pivot of rorated array */
    printf("New array: ");
    for (i < 0; i < size; i++) {
        new_arr[i] = arr[(pivot + i) % ARRAY_MAX]; 
        printf("%d ", new_arr[i]);
    }
    printf("\n");
    
    /*
     * With new array, there are a part is sorted from pivot to max.
     * And remaining is sorted from first to (pivot - 1).
     * So will do binary search of each part.
     */
    ret = binary_search(&new_arr[0], ARRAY_MAX - pivot, key);
    if (ret <= -2) {
        return -2;
    } else if (ret < 0) {
        ret = binary_search(&new_arr[ARRAY_MAX - pivot], pivot, key);
        if (ret >= 0)
            ret += ARRAY_MAX - pivot;
    }
        
    return ret;
}

/* Main func interrect with user */
int main()
{

    printf("Search %d in rotated array pivot %d -> pos %d\n", SEARCH_VAL,
           PIVOT_INDEX, search_rotated_array(rotated_array, ARRAY_MAX, PIVOT_INDEX, SEARCH_VAL));
    
    return 0;
}