Phương thức Array.BinarySearch trong C#

Giới thiệu

Array.BinarySearch tìm kiếm nhị phân (binary search) trên mảng đã sắp xếp. Trả về chỉ số 0-based của phần tử nếu tìm thấy, ngược lại trả về bitwise complement (~index) của vị trí chèn (số âm).

Yêu cầu bắt buộc

Mảng phải được sắp xếp trước theo thứ tự tăng dần (theo comparer mặc định hoặc custom). Nếu không, kết quả không xác định.

Ví dụ cơ bản

string[] str = { "a", "i", "m", "t" }; // Đã sắp xếp
int index = Array.BinarySearch(str, "t"); // 3

Ví dụ hoàn chỉnh

using System;

public class Demo
{
    public static void Main()
    {
        string[] str = { "a", "i", "m", "t" }; // Sorted!
        int res = Array.BinarySearch(str, "t");
        Console.WriteLine("Index: " + res);
    }
}

Kết quả

Index: 3

Giá trị trả về khi không tìm thấy

string[] arr = { "a", "c", "e" };
int idx = Array.BinarySearch(arr, "b"); // Không có "b"
if (idx < 0)
{
    int insertPos = ~idx; // Bitwise complement -> 1
    Console.WriteLine($"Không tìm thấy. Nên chèn tại index {insertPos}");
}

Các nạp chồng

• BinarySearch(Array, object)
• BinarySearch(Array, object, IComparer)
• BinarySearch<T>(T[], T)
• BinarySearch<T>(T[], T, IComparer<T>)
• Có overload với index, length để tìm trong đoạn con.

Lưu ý quan trọng

• Mảng phải sorted - đây là lỗi thường gặp nhất.
• Phức tạp O(log n) vs O(n) của Linear Search (IndexOf).
• Với duplicate, trả về index bất kỳ của các phần tử trùng (không đảm bảo đầu/cuối).
• Dùng Array.Sort trước khi BinarySearch nếu chưa sorted.