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 log2 (n), for both approaches. For the space complexity,
Recursive may reach to log2 (n) space because of the stack, but in the iterative approach, it should be O(1) space complexity.
