[Chia để trị] Tìm kiếm nhị phân

Mở loạt bài về giải thuật (thật sự thì trình em gà, học được gì share cái đó thôi), em nghĩ em sẽ bắt đầu trước từ thuật toán chia để trị (devide to conquer).

Về thuật toán chia để trị:

Thuật toán chia để trị

Trong khoa học máy tính, chia để trị là một mô hình thiết kế thuật toán quan trọng dựa trên đệ quy với nhiều phân nhánh. Thuật toán chia để trị hoạt động bằng cách chia bài toán thành nhiều bài toán nhỏ hơn thuộc cùng thể loại, cứ như vậy lặp lại nhiều lần, cho đến khi bài toán thu được đủ đơn giản để có thể giải quyết trực tiếp. Sau đó lời giải của các bài toán nhỏ được tổng hợp lại thành lời giải cho bài toán ban đầu. Kĩ thuật này là cơ sở cho nhiều thuật toán hiệu quả, chẳng hạn như thuật toá...

Ở đây, chắc mọi người đã quá quen với tìm kiếm nhị phân (binary search), và theo mình nghĩ (hướng dẫn thì cứ xưng như thế), mọi người thường dùng vòng lặp phải không (không phải cũng cứ coi như phải đi cho mình vui ) ? Vậy thì giờ đổi gió xíu nhé.

Tìm kiếm nhị phân

Trong khoa học máy tính, thuật toán tìm kiếm nhị phân là một thuật toán dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp. Thuật toán hoạt động như sau. Trong mỗi bước, so sánh phần tử cần tìm với phần tử nằm ở chính giữa danh sách. Nếu hai phần tử bằng nhau thì phép tìm kiếm thành công và thuật toán kết thúc. Nếu chúng không bằng nhau thì tùy vào phần tử nào lớn hơn, thuật toán lặp lại bước so sánh trên với nửa đầu hoặc nửa sau của danh sách. Vì số lượng phần tử trong danh sách cần xe...

Ý tưởng: Ta sẽ tìm xem giá trị cần tìm có nằm trong mảng không, nếu có, trả về chỉ số (index) của phần tử đó, không thì trả về -1. Tạm gọi thằng cần tìm là key đi ha (@nhatlonggunz bắt đầu chém gió từ đây, đa số mọi người đều biết về tìm kiếm nhị phân nên bỏ qua phần ý tưởng này cũng được)

• Đầu tiên ta xét thằng ở giữa (mid) xem có giống cái key không.

• Giống thì trả về thằng ở giữa, coi như chìa khóa đã tìm được lỗ… nhầm, ổ khóa
• Không giống thì sẽ có 2 trường hợp.
  1. Trường hợp cái chìa to hơn cái lỗ mid (key lớn hơn thằng ở mid), thì mình sẽ tìm những cái lỗ to hơn cái lỗ ở giữa (mid + 1 … cái lỗ to nhất có thể có)
  2. Trường hợp cái chìa bé hơn cái lỗ (key < thằng ở mid) thì tìm những cái lỗ nhỏ hơn cái lỗ ở giữa (từ thằng nhỏ nhất có thể có… mid - 1)
• Cứ lặp lại như thế
• Rồi sẽ tới lúc, chỉ còn 1 cái lỗ duy nhất, ở đây sẽ có 2 trường hợp nữa

1. Cái lỗ vừa khít với cái chìa => Đó là cái lỗ cần tìm
2. Cái lỗ không vừa => Chết, hết lỗ khóa rồi => Không có cái lỗ nào vừa với cái chìa. trả về -1)

Đưa về một chút cho hợp với đệ quy, ở đây không cách vào được nên viết mô tả (mã giã, pseudocode hay gì cũng được) hơi khó, thôi bỏ qua luôn đi. Nói chung là dùng đệ quy :v base case là khi mảng không còn phần tử nào (đầu mảng > cuối mảng)

CODE
------------------------------C++----------------------------------

int binarySearch(int A[], int key, int left, int right)
{
    if(left > right) // Đầu lớn hơn cuối => mảng không còn cái lỗ nào để cắm chìa vào nữa
        return -1; // => trả về -1

    else{

        int mid = (left + right) / 2;

        if(A[mid] == key) // Kiểm tra thằng ở giữa
            return mid;

        if(A[mid] > key) // Khi cái chìa nhỏ hơn cái lỗ
            return binarySearch(A, key, left, mid - 1);

        if(A[mid] < key) // khi cái chìa lớn hơn cái lỗ
            return binarySearch(A, key, mid + 1, right);
        }
}

Tìm kiếm nhị phân thường thì nên dùng vòng lặp
CODE
------------------------------C++----------------------------------

int binarySearch(int A[], int key, int left, int right)
{
    int mid;

    while(l < r) // Tìm đến khi chỉ còn 1 số duy nhất
    {
        mid = (l + r) / 2;

        if(A[mid] == key)
            break;
        else if(A[mid] > key)    // Khi cái Key nằm bên trái thằng mid
            r = mid - 1;
        else                     // Khi cái key năm bên phải
            l = mid + 1;
    }

    if(a[l] == key) return l;   // Nếu tìm được Key
    else -1;                    // Nếu như Key không tồn tại trong mảng
}

Em làm mấy bài cơ bản, mọi người gop ý