content: package Modified_Binary_Search;
  
  // Problem Statement: Search Bitonic Array (medium)
  // LeetCode Question:
  
  public class Problem_8_Search_Bitonic_Array {
  
      public int search(int[] arr, int key) {
          int maxIndex = findMax(arr);
          int keyIndex = binarySearch(arr, key, 0, maxIndex);
          if (keyIndex != -1)
              return keyIndex;
          return binarySearch(arr, key, maxIndex + 1, arr.length - 1);
      }
  
      // find index of the maximum value in a bitonic array
      public static int findMax(int[] arr) {
          int start = 0, end = arr.length - 1;
          while (start < end) {
              int mid = start + (end - start) / 2;
              if (arr[mid] > arr[mid + 1]) {
                  end = mid;
              } else {
                  start = mid + 1;
              }
          }
          return start;
      }
  
      // order-agnostic binary search
      private static int binarySearch(int[] arr, int key, int start, int end) {
          while (start <= end) {
              int mid = start + (end - start) / 2;
  
              if (key == arr[mid])
                  return mid;
  
              if (arr[start] < arr[end]) { // ascending order
                  if (key < arr[mid]) {
                      end = mid - 1;
                  } else { // key > arr[mid]
                      start = mid + 1;
                  }
              } else { // descending order
                  if (key > arr[mid]) {
                      end = mid - 1;
                  } else { // key < arr[mid]
                      start = mid + 1;
                  }
              }
          }
          return -1; // element is not found
      }
  }
  