int binarySearch(int arr[], unsigned int low, unsigned int high, int key)

{

if( low == high && arr[low] != key)

{

return -1;

}

unsigned int mid = low + (high - low)/2;

if(key == arr[mid])

{

return mid;

}

else if (key > arr[mid])

{

return binarySearch(arr, mid + 1, high, key);

}

else

{

return binarySearch(arr, low, mid - 1, key);

}

}

int search(int arr[], unsigned int low, unsigned int high, int key)

{

if( low == high && arr[low] != key)

{

return -1;

}

unsigned int mid = low + (high - low)/2;

if(key == arr[mid])

{

return mid;

}

else if(arr[mid] < arr[low]) // That means that the right half may be sorted

{

if((key > arr[mid]) && (key <= arr[high]))

{

return binarySearch(arr, mid + 1, high, key); //Here we know we just need to look

//into sorted part of array

}

else

{

return search(arr, low, mid-1, key);

}

}

else // That means that the Left half may be sorted

{

if((key >= arr[low]) && (key < arr[mid]))

{

return binarySearch(arr, low, mid - 1, key); //Here we know we just need to look

//into sorted part of array

}

else

{

return search(arr, mid + 1, high, key);

}

}

}

{

if( low == high && arr[low] != key)

{

return -1;

}

unsigned int mid = low + (high - low)/2;

if(key == arr[mid])

{

return mid;

}

else if (key > arr[mid])

{

return binarySearch(arr, mid + 1, high, key);

}

else

{

return binarySearch(arr, low, mid - 1, key);

}

}

int search(int arr[], unsigned int low, unsigned int high, int key)

{

if( low == high && arr[low] != key)

{

return -1;

}

unsigned int mid = low + (high - low)/2;

if(key == arr[mid])

{

return mid;

}

else if(arr[mid] < arr[low]) // That means that the right half may be sorted

{

if((key > arr[mid]) && (key <= arr[high]))

{

return binarySearch(arr, mid + 1, high, key); //Here we know we just need to look

//into sorted part of array

}

else

{

return search(arr, low, mid-1, key);

}

}

else // That means that the Left half may be sorted

{

if((key >= arr[low]) && (key < arr[mid]))

{

return binarySearch(arr, low, mid - 1, key); //Here we know we just need to look

//into sorted part of array

}

else

{

return search(arr, mid + 1, high, key);

}

}

}