/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
	}
	
	public void findInRotatedSortedArray(int[] arr, int target) {
        int n = arr.length;
        int low = 0, high = n - 1, maxVal = Integer.MIN_VALUE, maxIdx = -1, minVal = Integer.MAX_VALUE, minIdx = -1;

        //to check if the array is already sorted
        if (arr[low] < arr[high]) {
            binarySearch(0, n - 1, arr, target);
        }

        while (low <= high) {
            int mid = (low + high) / 2;

            if (arr[mid] > arr[n - 1]) {
                //value is on the left side
                //now to find if that value is max value in arr

                if (mid > 0 && mid < n - 1) {
                    if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                        maxVal = arr[mid];
                        maxIdx = mid;
                        minVal = arr[mid + 1];
                        minIdx = mid + 1;
                    } else {
                        low += mid + 1;
                    }
                }
            } else {
                if (mid > 0 && mid < n - 1) {

                    //to find the min value in arr
                    if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                        minVal = arr[mid];
                        minIdx = mid;
                        maxVal = arr[mid - 1];
                        maxIdx = mid - 1;
                    } else {
                        high = mid - 1;
                    }
                }
            }
        }

        if (target > minVal && target > arr[n - 1]) {
            binarySearch(0, maxIdx, arr, target);
        } else {
            binarySearch(minIdx, n - 1, arr, target);
        }
    }

    private void binarySearch(int low, int high, int[] arr, int target) {
    }
}