How to perform binary search in C#

The Array class in the system namespace provides the BinarySearch() method with multiple overloads that can be used to perform binary search in an array in C#.

Syntax

public static int BinarySearch (Array array, object? value);
  • This method takes a sortedascending order array and an object to search as input parameters.
  • It performs a binary search in the array. If the element is found, it returns the index of the element in the array.
  • If the element is not found, it returns a negative number.
  • It is important that we always pass the sorted arrayin increasing order as the input; otherwise, it can return incorrect results.
  • The input array can contain duplicate elements. If the array contains more than one occurrence of the search object, an index of only one of the occurrences is returned, and it is not necessarily the first occurrence.
  • The time complexity of this method is O(logn), as it performs a binary search on the array.

In the example in the code below, we have created a simple wrapper method that takes an array and object to search, and prints if the element is present in the array along with its index.

We call the wrapper method with a sorted integer array and sorted array of strings.

The Array.BinarySearch() method is called on these inputs, and the search element and its index are printed if found in the array.

In the case of duplicates, the search stops as soon as the binary search finds an instance of the search element. It is important to note that this might not necessarily be the first occurrence. All other instances would be ignored.

The program prints the output below and exits.

Item 44 is at index : 3
Item 99 is not present in the array
Item car is at index : 2
Item elephant is not present in the array
using System;
class HelloWorld
{
static void Main()
{
int[] numArray = new int[] { 11, 22, 33, 44, 55, 66, 77 };
SearchArray(numArray, 44);
SearchArray(numArray, 99);
string[] elements = {"apple", "banana", "car", "dog"};
SearchArray(elements, "car");
SearchArray(elements, "elephant");
}
public static void SearchArray(Array array, object value)
{
int numIndex = Array.BinarySearch(array, value);
if(numIndex > 0)
{
Console.WriteLine("Item {0} is at index : {1}",value, numIndex);
} else
{
Console.WriteLine("Item {0} is not present in the array", value);
}
}
}