Tìm kiếm nhị phân trong C# Hướng dẫn và ví dụ thực hành

Để viết thuật toán tìm kiếm nhị phân để tìm một phần tử trong một mảng đã được sắp xếp trong C#, chúng ta cần hiểu rõ cách hoạt động của thuật toán này. Tìm kiếm nhị phân là một phương pháp tìm kiếm hiệu quả, đặc biệt là đối với các mảng đã được sắp xếp. Nó sử dụng chiến lược chia để trị để giảm một nửa phạm vi tìm kiếm sau mỗi lần kiểm tra, điều này giúp tăng tốc độ tìm kiếm đáng kể so với tìm kiếm tuyến tính.

Dưới đây là một phiên bản chi tiết và đầy đủ của thuật toán tìm kiếm nhị phân trong C#:

using System;

class BinarySearchExample
{
    // Hàm tìm kiếm nhị phân
    public static int BinarySearch(int[] array, int target)
    {
        int left = 0;               // Chỉ số bắt đầu của mảng
        int right = array.Length - 1; // Chỉ số kết thúc của mảng

        while (left <= right)
        {
            // Tính toán chỉ số giữa
            int mid = left + (right - left) / 2;

            // Kiểm tra nếu phần tử giữa là phần tử cần tìm
            if (array[mid] == target)
            {
                return mid; // Trả về chỉ số của phần tử nếu tìm thấy
            }

            // Nếu phần tử cần tìm lớn hơn phần tử giữa, bỏ qua nửa trái
            if (array[mid] < target)
            {
                left = mid + 1;
            }
            // Nếu phần tử cần tìm nhỏ hơn phần tử giữa, bỏ qua nửa phải
            else
            {
                right = mid - 1;
            }
        }

        return -1; // Trả về -1 nếu không tìm thấy phần tử
    }

    // Hàm chính để chạy chương trình
    static void Main(string[] args)
    {
        // Khởi tạo mảng đã được sắp xếp
        int[] array = { 3, 9, 10, 27, 38, 43, 82 };
        int target = 43; // Phần tử cần tìm

        // In ra mảng đã sắp xếp và phần tử cần tìm
        Console.WriteLine("Mảng đã sắp xếp: " + string.Join(", ", array));
        Console.WriteLine("Phần tử cần tìm: " + target);

        // Gọi hàm BinarySearch để tìm phần tử trong mảng
        int index = BinarySearch(array, target);

        // In ra kết quả tìm kiếm
        if (index != -1)
        {
            Console.WriteLine("Phần tử " + target + " được tìm thấy tại chỉ số: " + index);
        }
        else
        {
            Console.WriteLine("Phần tử " + target + " không có trong mảng.");
        }
    }
}

Giải thích chi tiết:

1. BinarySearch Method:

   • Tham số:
     • array: Mảng các số nguyên đã được sắp xếp.
     • target: Phần tử cần tìm trong mảng.
   • Biến:
     • left: Chỉ số bắt đầu của phạm vi tìm kiếm (ban đầu là 0).
     • right: Chỉ số kết thúc của phạm vi tìm kiếm (ban đầu là chiều dài của mảng trừ 1).
   • Thuật toán:
     • Trong khi phạm vi tìm kiếm không rỗng (left <= right):
       • Tính chỉ số giữa mid của phạm vi hiện tại.
       • Nếu phần tử ở chỉ số giữa (array[mid]) bằng với phần tử cần tìm (target), trả về chỉ số giữa.
       • Nếu phần tử ở chỉ số giữa nhỏ hơn phần tử cần tìm, điều chỉnh phạm vi tìm kiếm sang nửa phải (left = mid + 1).
       • Nếu phần tử ở chỉ số giữa lớn hơn phần tử cần tìm, điều chỉnh phạm vi tìm kiếm sang nửa trái (right = mid - 1).
     • Nếu không tìm thấy phần tử cần tìm trong phạm vi tìm kiếm, trả về -1.

2. Main Method:

   • Khởi tạo mảng các số nguyên đã được sắp xếp và giá trị phần tử cần tìm.
   • In ra mảng và phần tử cần tìm để người dùng dễ theo dõi.
   • Gọi hàm BinarySearch để tìm phần tử trong mảng và lưu chỉ số của phần tử tìm được.
   • In ra kết quả tìm kiếm, cho biết phần tử cần tìm có trong mảng hay không và nếu có thì ở chỉ số nào.

Ưu điểm của Tìm kiếm Nhị phân:

• Tìm kiếm nhị phân có độ phức tạp thời gian là $O(\log n)$, nhanh hơn nhiều so với tìm kiếm tuyến tính với độ phức tạp $O(n)$, đặc biệt là với các mảng lớn.
• Hiệu quả khi mảng đã được sắp xếp.

Nhược điểm của Tìm kiếm Nhị phân:

• Yêu cầu mảng phải được sắp xếp trước. Nếu mảng chưa được sắp xếp, bạn cần phải sắp xếp mảng trước khi thực hiện tìm kiếm nhị phân, điều này có thể làm tăng thời gian xử lý tổng thể.

Chương trình trên giúp bạn dễ dàng tìm kiếm một phần tử trong một mảng đã được sắp xếp bằng cách sử dụng thuật toán tìm kiếm nhị phân trong C#. Bạn có thể chạy và thử nghiệm chương trình để hiểu rõ hơn về cách thức hoạt động của thuật toán này.