C#

Recursive Binary search in C#

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(logn). 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

Demonstration of Recursive Binary search in C#
Demonstration of Recursive Binary search in C#

Further Reading

Selection Sort in C#

Insertion Sort in C#

Bubble Sort in C#

How to Create Instance Variables and Class Variables in Python

Comparing Rows of Two Tables with ADO.NET

Example of Label and Textbox Control in ASP.NET

One Dimensional and Two Dimensuonal Indexers in C#

Private and Static Constructors in C#

Methods of Array Class

Anonymous Functions in C#

Programs to Find Armstrong Numbers in C#

Matrix Multiplication in C#

One Dimensional and Two Dimensional Indexers in C#

Static Class Example in C#

Rotating an Array in C#

Generic IList Interface and its Implementation in C#

Recursive Binary search in C#

C# Practice Questions

Creating Navigation Window Application Using WPF in C#

Find Intersection Using Arrays

An array of Objects and Object Initializer

Performing Set Operations in LINQ

Using Quantifiers in LINQ

Data Binding Using BulletedList Control

Grouping Queries in LINQ

Generic Binary Search in C#

Understanding the Quantifiers in LINQ

Join Operation using LINQ

Deferred Query Execution and Immediate Query Execution in LINQ

Examples of Query Operations using LINQ in C#

An array of Objects and Object Initializer

Language-Integrated Query (LINQ) in C#

How Data Binding Works in WPF

Examples of Connected and Disconnected Approach in ADO.NET

New Features in C# 9

IEnumerable and IEnumerator Interfaces

KeyValuePair and its Applications

C# Root Class – Object

Access Modifiers in C#

Learning Properties in C#

Learning All Class Members in C#

Examples of Extension Methods in C#

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

Understanding the Concept of Nested Classes in C#

LINQ To SQL Examples

A Beginner’s Tutorial on WPF in C#

Explaining C# Records with Examples

Everything about Tuples in C# and When to Use?

Creating Jagged Arrays in C#

Linear Search and Binary search in C#

Learning Indexers in C#

Object Initializers in C#

Examples of Static Constructors in C#

When should We Use Private Constructors?

C# Basic Examples

IEqualityComparer Interface

programmingempire

You may also like...