#include <stdio.h>
int binarySearch(int arr[], int low, int high, int x) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);
return binarySearch(arr, mid + 1, high, x);
}
return -1;
}
int findPivot(int arr[], int low, int high) {
if (high < low)
return -1;
if (high == low)
return low;
int mid = low + (high - low) / 2;
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
if (mid > low && arr[mid] < arr[mid - 1])
return (mid - 1);
if (arr[low] >= arr[mid])
return findPivot(arr, low, mid - 1);
return findPivot(arr, mid + 1, high);
}
int pivotedBinarySearch(int arr[], int n, int x) {
int pivot = findPivot(arr, 0, n - 1);
if (pivot == -1)
return binarySearch(arr, 0, n - 1, x);
if (arr[pivot] == x)
return pivot;
if (arr[0] <= x)
return binarySearch(arr, 0, pivot - 1, x);
return binarySearch(arr, pivot + 1, n - 1, x);
}
int main() {
int arr[] = {4, 5, 6, 7, 8, 9, 1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 6;
int result = pivotedBinarySearch(arr, n, x);
printf("Index of %d in the rotated array is %d\n", x, result);
return 0;
}