using System;

namespace MyCompiler {
    class Program {
        public static void Main(string[] args) {
            int[] myArr = {1,2,3,4,5,6,7,8,9,11,13,14};
            int[] newArr = {14,11,9,8,7,6,5,4,3,2,1};
            int target = 12;
            Console.WriteLine("Normal Binary Search : Index Of Target Element => "
                                    +SearchNumber(myArr,target));
            Console.WriteLine("Agnostic Binary Search : Index Of Target Element => "
                                +OrderAgnosticBinary(newArr,target));
        }

        static int SearchNumber(int[] arr,int target){
            int start = 0;
            int end = arr.Length - 1;
            while(start<=end){
                int middle = start + (end - start)/2;

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

        // Order Agnostic Binary Search
        static int OrderAgnosticBinary(int[] arr,int target1){
            int start = 0;
            int end = arr.Length - 1;

            //Check Weather array is ascending or decending order
            bool isAcs = arr[start] < arr[end];
            
            while(start<=end){
                int middle = start + (end - start)/2;

                if(arr[middle] == target1){
                    return middle;
                }

                if(isAcs){
                    if(target1 < arr[middle]){
                        end = middle - 1;
                    }else{
                        start = middle + 1;
                    }
                }else{
                    if(target1 > arr[middle]){
                        end = middle - 1;
                    }else{
                        start = middle + 1;
                    }
                }
            }
            return -1;
        }
        
    }
}