How to Use List.BinarySearch in C# for Fast Searching

Use List.BinarySearch in C# to quickly find the index of an item in a sorted list. It returns the index if found, or a negative number if not found. Make sure the list is sorted before calling BinarySearch for correct results.

Syntax

The List.BinarySearch method searches a sorted list for a specific element and returns its index if found.

Basic syntax:

• int index = list.BinarySearch(item); - Searches for item in the entire list.
• int index = list.BinarySearch(index, count, item, comparer); - Searches a range with a custom comparer.

Parameters explained:

• item: The element to search for.
• index: The starting index of the range to search.
• count: The number of elements in the range to search.
• comparer: An optional object to define custom comparison rules.

csharp

int index = list.BinarySearch(item);
int index = list.BinarySearch(index, count, item, comparer);

Example

This example shows how to use List.BinarySearch to find an integer in a sorted list. It prints the index if found or a message if not found.

csharp

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> numbers = new List<int> { 1, 3, 5, 7, 9 };
        int target = 5;

        // List must be sorted for BinarySearch to work correctly
        numbers.Sort();

        int index = numbers.BinarySearch(target);

        if (index >= 0)
        {
            Console.WriteLine($"Found {target} at index {index}.");
        }
        else
        {
            Console.WriteLine($"{target} not found in the list.");
        }
    }
}

Output

Found 5 at index 2.

Common Pitfalls

Common mistakes when using List.BinarySearch include:

• Unsorted list: The list must be sorted before calling BinarySearch. Otherwise, the result is unpredictable.
• Ignoring negative results: If the item is not found, BinarySearch returns a negative number, not -1. This negative number can be used to find the insertion point.
• Wrong comparer: Using a comparer that does not match the list's sorting order leads to incorrect results.

Example of wrong usage and fix:

csharp

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> numbers = new List<int> { 3, 1, 9, 7, 5 };
        int target = 5;

        // Wrong: list is not sorted
        int wrongIndex = numbers.BinarySearch(target);
        Console.WriteLine($"Wrong index (unsorted list): {wrongIndex}");

        // Correct: sort the list first
        numbers.Sort();
        int correctIndex = numbers.BinarySearch(target);
        Console.WriteLine($"Correct index (sorted list): {correctIndex}");
    }
}

Output

Wrong index (unsorted list): -1
Correct index (sorted list): 2

Quick Reference

Tips for using List.BinarySearch:

• Always sort the list before searching.
• Check if the returned index is negative to know if the item was not found.
• Use the overload with comparer for custom sorting rules.
• The negative return value can be converted to insertion index by ~index.

Key Takeaways

Always sort your list before using List.BinarySearch for accurate results.

List.BinarySearch returns the index of the item if found, otherwise a negative number.

Use the negative return value to find where the item could be inserted to keep the list sorted.

You can provide a custom comparer to BinarySearch for special sorting rules.

Ignoring sorting or the negative result can cause bugs or wrong search results.