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 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 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(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**_{2} (n), for both approaches. For the space complexity,

Recursive may reach to **log**_{2} (n) space because of the stack, but in the iterative approach, it should be **O(1)** space complexity.