October 13, 2021

Programmingempire

The following code example demonstrates the Recursive Binary search in C#. Basically, searching is a very important algorithm in computer science. In fact, almost every application requires the use of searching. Hence, an efficient implementation of the searching algorithm can have substantial improvement in the overall performance of the applications.

Searching Techniques

In short, there are two widely used searching techniques.

Linear Search
Binary Search

While the linear search performs iteration over all elements in the list until the target element is found or the end of the list is reached. But, the binary search works in a different manner. In this case, first, the binary search function computes the value of the middle index of the list. In other words, the middle index is computed by dividing the sum of the smallest value of the index and the largest value of the index by 2. After that, the target element is compared with the element at the middle index. Once, a match is found, the process exits. Otherwise, it determines whether the target is smaller than the middle element or larger. Accordingly, it discards the second half of the list in case the target is smaller than the middle element. Likewise, in the latter case, it discards the first half of the list.

Hence, binary search doesn’t make a comparison with all elements of the list. Therefore it is much more efficient in comparison to the linear search. In fact, binary search has a time complexity of O(log_n). While, the linear search has a time complexity of O(n), where n is the number of elements in the list.

Recursive Implementation of the Binary Search

The following code shows the use of a recursive function, RecursiveBinarySearch(), that calls itself recursively, if the target is not yet found and there are still elements in the list.

using System;

namespace RecursiveBinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = {78, 1, 6, 37, 96, 567, 123, 579, 23, 8, 18, 28, 58, 45, 2, 76};
            Console.WriteLine("Unsorted Array...");
            foreach (int x in arr)
                Console.Write(x + " ");
            Console.WriteLine();
            Array.Sort(arr);
            Console.WriteLine("Sorted Array...");
            foreach (int x in arr)
                Console.Write(x + " ");
            Console.WriteLine();
            Console.WriteLine("Enter the target value to search: ");
            int p = Int32.Parse(Console.ReadLine());
            int pos = RecursiveBinarySearch(arr, 0, arr.Length - 1, p);
            if(pos!=-1)
               Console.WriteLine("Target found at index "+pos);
            else
               Console.WriteLine("Target not found!");
        }
        public static int RecursiveBinarySearch(int[] a, int min, int max, int t)
        {
                int mid = (min + max) / 2;
                if (a[mid] == t)
                {
                    return mid;
                }
                if (a[mid] > t)
                {
                    return   RecursiveBinarySearch(a, min, mid - 1, t);
                }
            if (max < min) return -1;
            
            return RecursiveBinarySearch(a, mid + 1, max, t);
        }
    }
}

Output

Programmingempire

Searching Techniques

Recursive Implementation of the Binary Search

Further Reading

You may also like...

Anonymous Functions in C#

Comparing Rows of Two Tables with ADO.NET

New Features in C# 9