Phương thức Array.BinarySearch(Array, Int32, Int32, Object) trong C# với ví dụ

Giới thiệu

Phương thức Array.BinarySearch() trong C# tìm kiếm một giá trị trong một phạm vi (range) của mảng một chiều đã sắp xếp (sorted), sử dụng interface IComparable được triển khai bởi từng phần tử và giá trị tìm kiếm.

Lưu ý quan trọng: Mảng phải được sắp xếp trước theo thứ tự tăng dần. Nếu không, kết quả không xác định.

Cú pháp

public static int BinarySearch (Array array, int index, int length, object value);

• array: mảng một chiều cần tìm kiếm.
• index: chỉ số bắt đầu của phạm vi tìm kiếm (0-based).
• length: độ dài của phạm vi tìm kiếm.
• value: đối tượng cần tìm.

Giá trị trả về

• ≥ 0: Chỉ số (index) của phần tử tìm thấy trong mảng.
• < 0: Không tìm thấy. Giá trị trả về là bitwise complement (~index) của vị trí chèn để giữ mảng có thứ tự. Công thức: ~index = -index - 1. Vị trí chèn = ~returnValue.

Ví dụ 1: Tìm thấy phần tử

using System;

public class Demo {
    public static void Main() {
        int[] intArr = {10, 20, 30, 40, 50};
        Array.Sort(intArr); // Đảm bảo sắp xếp (đã sẵn)

        Console.WriteLine("Các phần tử mảng...");
        foreach(int i in intArr) {
            Console.WriteLine(i);
        }

        // Tìm 20 trong phạm vi index 1, length 3 (phần tử 20, 30, 40)
        int result = Array.BinarySearch(intArr, 1, 3, 20);
        Console.WriteLine("Phần tử 20 ở index = " + result);
    }
}

Đầu ra ví dụ 1

Các phần tử mảng...
10
20
30
40
50
Phần tử 20 ở index = 1

Ví dụ 2: Không tìm thấy phần tử

using System;

public class Demo {
    public static void Main() {
        int[] intArr = {5, 10, 15, 20};
        Array.Sort(intArr);

        Console.WriteLine("Các phần tử mảng...");
        foreach(int i in intArr) {
            Console.WriteLine(i);
        }

        // Tìm 25 trong phạm vi index 0, length 2 (chỉ phần tử 5, 10)
        int result = Array.BinarySearch(intArr, 0, 2, 25);
        Console.WriteLine("Phần tử 25 ở index = " + result);
    }
}

Đầu ra ví dụ 2

Các phần tử mảng...
5
10
15
20
Phần tử 25 ở index = -3

Giải thích kết quả -3

Giá trị trả về -3 nghĩa là không tìm thấy. Vị trí chèn để giữ thứ tự: ~(-3) = 2. Nghĩa là 25 nên được chèn vào index 2 (giữa 10 và 15). Tuy nhiên phạm vi tìm kiếm chỉ length=2 (index 0,1), nên 25 lớn hơn mọi phần tử trong phạm vi.

Các overload BinarySearch khác

Lưu ý quan trọng

• Mảng phải sắp xếp tăng dần theo cùng comparer dùng để tìm kiếm.
• Với kiểu tự định nghĩa, triển khai IComparable<T> hoặc cung cấp IComparer<T>.
• Độ phức tạp: O(log n) - nhanh hơn nhiều so với Linear Search O(n).
• Generic overload Array.BinarySearch<T>() khuyến nghị dùng cho type safety và tránh boxing.

Ví dụ Generic (khuyến nghị)

using System;

public class Demo {
    public static void Main() {
        int[] arr = { 10, 20, 30, 40, 50 };
        int index = Array.BinarySearch(arr, 30); // Generic overload
        Console.WriteLine("Index của 30: " + index); // 2

        int notFound = Array.BinarySearch(arr, 25);
        Console.WriteLine("Index của 25: " + notFound); // -3 (~2)
        Console.WriteLine("Vị trí chèn 25: " + ~notFound); // 2
    }
}