public class Main {
    public static void main(String[] args) {
        //int [] arr= {1,2,3,4,5,6,7,8,9,10};
        int [] arr= {99,98,97,96,87,65,54,52,13}; // works in ascendign or descendin array
        int target = 65; // which element are we looking for
        int ans=orderAgnosticBinarySearch(arr,target);
        System.out.println(ans);
        
    }
    static int orderAgnosticBinarySearch(int[] arr,int target){
        int start=0;
        int end=arr.length-1;

        //find whether the array is sorted in ascending or descending

        boolean isAscending=arr[start] < arr[end];
        
        while (start<=end){
            int mid=start+(end-start)/2;

            if(arr[mid]==target){
                return mid;
            }

            if(isAscending)
                if(target<arr[mid]){
                    end=mid-1;
                }
                else{
                    start=mid+1;
                }
            else{
                if(target>arr[mid]){
                    end=mid-1;
                }else{
                    start=mid+1;
                }
            }
        }
        return -1;
    }
}