It is a divide and conquer approach to search an element in the Array. At each step, the search space is reduced to half. The input array would be already be sorted.

The first part of the program is a recursive approach to write the Binary Search algorithm. The second approach focuses on the iterative model. The code will spit out the index of the element if found.

public class BinarySearch
    {
        //space and time complexity: O(log2 (n)).
        public int? fnRecursiveBinarySearch(int[] Arr, int k, int low, int high)
        {
            int mid = 0;
            if (low > high)
            {
                return null;
            }
            else
            {
                mid = (high + low) / 2;
                if (k==Arr[mid])
                {
                    return mid;
 //return position of found.
                }
                else if (k < Arr[mid])
                {
                    return fnRecursiveBinarySearch(Arr, k, low, mid - 1);
 //search in first half.
                }
                else
                {
                    return fnRecursiveBinarySearch(Arr, k, mid + 1, high);
 //search in second half.
                }
            }
        }

        //space complexity: O(1) and time complexity: O(log2 (n))
        public int? fnIterativeBinarySearch(int[] Arr, int k, int low, int high)
        {
            int mid = 0;
            do
            {
                mid = (low + high) / 2;
                if(k==Arr[mid]) { return mid; //return position of found. }
                else if(k<Arr[mid]) {
                    high = mid - 1;
 //search in first half.
                }
                else
                {
                    low = mid + 1;
 //search in second half.
                }
            } while (low <= high);
            return null;
        }

    }

To test the above 2 approaches, we use a simple call to both the functions:

class Program
    {
        static void Main(string[] args)
        {
            BinarySearch bs = new BinarySearch();
            int[] Arr = { 5, 6, 3, 1, 8, 10 };

            Console.WriteLine("Recursively Found element at index: {0}", bs.fnRecursiveBinarySearch(Arr, 8, 0, Arr.Length - 1));
            Console.WriteLine("Iteratively Found element at index: {0}", bs.fnIterativeBinarySearch(Arr, 8, 0, Arr.Length - 1));
        }
    }

Time complexity is log₂ (n), for both approaches. For the space complexity,
Recursive may reach to log₂ (n) space because of the stack, but in the iterative approach, it should be O(1) space complexity.

Python implementation for Binary Search Recursive approach:

Space and time complexity: O(log2 (n))

def binarySearch(array, target):
   return binarySearchHelper(array, target, 0, len(array) - 1)
	
def binarySearchHelper(array, target, left, right):
	if left > right:
		return -1
	middle = (left + right) // 2
	potentialMatch = array[middle]
	if target == potentialMatch:
		return middle
	elif target < potentialMatch:
		return binarySearchHelper(array, target, left, middle - 1)
	else:
		return binarySearchHelper(array, target, middle + 1, right)

Python implementation for Binary Search Iterative approach:

Space complexity: O(1) and time complexity: O(log2 (n))

def binarySearch(array, target):
    left = 0
	right = len(array) - 1
	while left <= right:
		middle = (left + right) // 2
		potentialMatch = array[middle]
		if target == potentialMatch:
			return middle
		elif target < potentialMatch:
			right = middle - 1
		else:
			left = middle + 1
	return -1