using System;

namespace MyCompiler {
    class Program {
        public static void Main(string[] args) {
            int[] myArr = {1,2,5,7,11,12,15,19,20,22,34,45,67,89,99,100,101};
            int target = 89;
            Console.WriteLine("Index of target element is : "+answer(myArr,target));
        }

        static int answer(int[] arr, int target){
            int start = 0;
            int end = 1;

            //condition for element to lie between range
            while(target > arr[end]){
                int temp = end + 1; // new start
                //double the box value & end = previous end * size of box
                end = end + (end - start + 1)*2;
                start = temp;
            }

            return binarySearch(arr,target,start,end);
        }

        static int binarySearch(int[] arr,int target,int start,int end){
            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 -1;
        }
    }
}