[ARRAY] Binary Search on a Sorted Array

Problem: Write a function to perform a binary search on a Sorted Array.

Solution: The recursive solution below runs in O(log(n)) because the problem size is halved with each recursive call.

// returns the index of the target element if found, else returns -1
        static int Binary_Search(int[] arr, int start, int end, int target)
        {
           int medianIndex = (end - start) /2 + start;
           int medianValue = arr[medianIndex];

           if(start == end && arr[start] != target)
               return -1;
           if (medianValue == target)
               return medianIndex;
           else if (medianValue < target)
               return Binary_Search(arr, medianIndex + 1, end, target);
           else
               return Binary_Search(arr, start, medianIndex - 1, target);
        }

END