worst case

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