Binary Search with C#

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.