# 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**

**Further Reading**

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#

Programs to Find Armstrong Numbers in C#

One Dimensional and Two Dimensional Indexers in C#

Generic IList Interface and its Implementation in C#

Creating Navigation Window Application Using WPF in C#

Find Intersection Using Arrays

An array of Objects and Object Initializer

Performing Set Operations in LINQ

Data Binding Using BulletedList Control

Understanding the Quantifiers in 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#

Examples of Connected and Disconnected Approach in ADO.NET

IEnumerable and IEnumerator Interfaces

KeyValuePair and its Applications

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#

A Beginner’s Tutorial on WPF in C#

Explaining C# Records with Examples

Everything about Tuples in C# and When to Use?

Linear Search and Binary search in C#

Examples of Static Constructors in C#