C#

Recursive Binary Search in C#

Basically, binary search is an efficient way to search a given value from a list of values. The following code example shows Recursive Binary Search in C#.

So, let us assume that we have a linear data structure such as an array. Our aim is to find a particular target value in the array. As can be seen, we can compare the target value with each of the values present in the array until we find a match. However, there is a much efficient way.

Accordingly, we compare the target value with the middle element of the array. If the target is smaller, we discard the second half of the array. Otherwise, we discard the first half. This procedure is repeated until either we find a match or the minimum index exceeds the maximum. In such a case, the target element is not present in the array.

The following code shows a recursive function that returns the index if the target is found. Otherwise, it returns -1. As can be seen, there are two recursive calls indicating the target is smaller than the middle element or larger.

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);
            Console.WriteLine(pos);
        }
        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

Demonstration of Recursive Binary Search in C#
Demonstration of Recursive Binary Search in C#


Related Topics

A Beginner’s Tutorial on WPF in C#

Everything about Tuples in C# and When to Use?

Linear Search and Binary Search in C#

Creating Jagged Arrays in C#

When should We Use Private Constructors?

C# Practice Questions

C# Basic Examples

Private and Static Constructors in C#

Constructors in C#

C# Arrays

C# Examples

How to Create a C# Console Application

Creating Navigation Window Application Using WPF in C#

LINQ To SQL Examples

Understanding the Concept of Nested Classes in C#

How to Setup a Connection with SQL Server Database in Visual Studio

C# Root Class – Object

KeyValuePair and its Applications

IEnumerable and IEnumerator Interfaces

IEqualityComparer Interface

New Features in C# 9

Generic IList Interface and its Implementation in C#

Examples of Connected and Disconnected Approach in ADO.NET

How Data Binding Works in WPF

Language-Integrated Query (LINQ) in C#

Examples of Query Operations using LINQ in C#

Join Operation using LINQ

Deferred Query Execution and Immediate Query Execution in LINQ

Understanding the Quantifiers in LINQ

Grouping Queries in LINQ

Generic Binary Search in C#

Leave a Reply

Your email address will not be published. Required fields are marked *