using System;

namespace MyCompiler {
    class Program {
        public static void Main(string[] args) {
            char[] arr = {'c','f','g','h'};//{1,2,4,5,7,11,14,16};
            char target = 'd';
            Console.WriteLine("Ceiling nearest to target at index : "+ceilingNumber(arr,target));
            // Console.WriteLine("Floor nearest to target at index : "+floorNumber(arr,target));
        }

        //ceiling return the greatest number equal to or greated then target number
        static char ceilingNumber(char[] arr,char target){
            int start = 0;
            int end = arr.Length - 1;

            // if(target > arr[end]){
            //     return arr[start];
            // }

            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 arr[middle];
                }
            }
            return arr[start];
        }

        //Floor Return greatest number equal to or less then the target number
        static int floorNumber(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;
        }
    }
}