content: package search;
  
  
  public class RotatedBinarySearch {
  
  
      /*
       * Binary Search using recursion
       * Time complexity - Olog(n)
       * Memory Complexity - O(logn) - as it will consume memory on the stack
       * */
      public static int rotatedBinarySearch(int[] arr, int n, int low, int high) {
          if(low > high) return -1;
  
          int middle = low + ((high-low)/2);
          if(arr[middle] == n) return middle;
  
          /*
           * Step 1: check if the n value is less than the middle value
           * Step 2: Check if the first value is less than the middle value
           * Step 3: Check if the first value is less than the n value
           * */
          if(n < arr[middle] && arr[low] < arr[middle] && n>= arr[low]) {
              return rotatedBinarySearch(arr, n, low, middle-1);
  
          /*
           * Step 1: check if the n value is greater than the middle value
           * Step 2: Check if the middle value is less than the highest value
           * Step 3: Check if the highest value is <= the n value
           * */
  
          } else if(n > arr[middle] && arr[middle] < arr[high] && n <= arr[high]) {
              return rotatedBinarySearch(arr, n, middle+1, high);
  
          /*
           * Step 1: check if the first value is greater than the middle value
           * */
  
          } else if(arr[low] > arr[middle]) {
              return rotatedBinarySearch(arr, n, low, middle-1);
  
          /*
           * Step 1: check if the last value is less than the middle value
           * */
          } else if(arr[high] < arr[middle]) {
              return rotatedBinarySearch(arr, n, middle+1, high);
          }
  
          return -1;
      }
  
  
      public static void main(String[] args) {
          int[] arr = {5, 6, 7, 8, 9, 10, 1, 2, 3};
          int n = 3;
          System.out.println(rotatedBinarySearch(arr, n, 0, arr.length-1));
      }
  }
  