3 Ways to Implement Binary Search Program in C#

Binary search is the fastest way to implement the searching on the sorted collection (data). C# provides you with some built-in methods as well to implement the binary search. But you are always free to write your own implementations for binary search.

What is Binary Search

In a binary number system, we have only two digits 0 & 1. Similarly in the binary search, we will have only two sides. These sides will be available in our collection by finding a midpoint and we will find out our data either on the left side or on the right side of the midpoint.

Show me the Code

We (developers) love the code. So it would be better to understand the concept using the actual collection of data (int in our case).

I have an int array and I want to search number 5.

int[] array = { 1,5,8,10,12 };

Using built-in method by C#

BinarySearch() is a built-in method in the Array class. We can use this method to search the number without writing any custom code.

BinarySearch() for Array:

Array.BinarySearch(array, 5);
// Where array is the collection of data 
// and 5 is the number that we are looking for.

This will return an index (int) for the target number.

Binary search for Generic Collection like List<>:

Let’s assume we need to implement the Binary Search on the list. This is what it will look like.

List<int> array = new() { 1, 5, 8, 10, 12 };
var result = array.BinarySearch(number);

In this way, we can use the BinarySearch method just like the extension method and simply pass the value that you are searching for as a parameter.

Okay But I am the interviewer 🙄. Show me the custom implementation of Binary Search in C# 😎.

In reality, the developers prefer to use the built methods but don’t know why the interviewers need to see the custom code.

Let’s think about it before writing the code. How the binary search algorithm would work.

• Make sure the data is in sorted order (either in ascending or descending order). Here I am assuming the data is sorted in ascending order.
• Now we will use two variables min & max.(Feel free to rename the variables if you don’t like them.) These variables are used for the boundaries of the array.
• In the first iteration, we will assign min = 0 & max = array.Length -1
• Find out a third variable mid by using (min+max)/2.
• If the given number is less than the array[mid], which means the number lies on the left side from mid then we will reassign the max to mid-1 and will go to 4th step.
• In case the number is greater than the array[mid], which means the number lies on the right side of the mid then we will reassign the min to mid+1 and will go to 4th step.
• Remember to check if array[mid] == number then we got what we were looking for and we will simply return the mid (This indicates the index of the target).
• After these assignments if min > max, then this simply means that the number that we are looking for does not exist in the input array.

Let’s create a C# method for Binary Search Program using the above steps.

public static int BinarySearchLinear(int[] array, int number)
{
    if (array?.Any() != true)
    {
        return -1;
    }
    int min = 0;
    int max = array.Length - 1;

    while (min <= max)
    {
        int mid = (min + max) / 2;

        if (array[mid] == number)
        {
            return mid;
        }

        else if (number < array[mid])
        {
            max = mid - 1;
        }
        else
        {
            min = mid + 1;
        }
    }

    return -1;
}

Does the above code make sense to you? If not read the above steps again carefully and then focus on the code. For better understanding make sure to debug the execution line by line.

Can you write the Binary Search program using Recursion in C#?

Of course, I can. If the above logic is clear then we can simply implement the recursion concept by making some small changes.

The process of calling a method by itself as a child is called as Recursion.

Here is the Binary Search Program using Recursion in C#

public static int BinarySearchRecursion(List<int> array, int number, int min, int max)
{
    int mid = (min + max) / 2;

    if (array[mid] == number)
    {
        return mid;
    }

    else if (number < array[mid])
    {
        max = mid - 1;
    }
    else
    {
        min = mid + 1;
    }

    if (max < min)
    {
        return -1;
    }

    return BinarySearchRecursion(array, number, min, max);
}

See, the logic is the same but now are executing the same logic by using recursion.

Feel free to ask your questions and doubts in the comment section below and Thankyou for reading it.