Tìm kiếm nhị phân | Binary search

Chào mừng các bạn đã đến với thachleblog, bài viết hôm nay mình sẽ trình bày về một thuật toán tìm kiếm đơn giản nhưng lại cực kỳ hiệu quả, được ứng dụng rất nhiều trong thực tế đó là tìm kiếm nhị phân hay còn gọi là binary search. Nào, chúng ta cùng bắt đầu nhé.

Giới thiệu

Nói về bài toán tìm kiếm, chúng ta gặp rất nhiều trong thực tế đó là khi chúng ta tìm tên mình danh sách đăng ký vận động viên marathon, tìm tên mình trong danh sách nhân viên xuất sắc của năm được dán ở đâu đó. Thời đại này cần tìm kiếm thì nhấn nút thôi chứ lấy ví dụ về tìm kiếm bằng mắt khó quá, hehe.

Cách đơn giản nhất là chúng ta sẽ dò tuần tự (đối với các danh sách ngắn), cho đến khi tìm đúng đến tên mình. Hoặc cũng có cách nhanh hơn là vì các danh sách thường sắp xếp theo tên, do đó, mình chỉ việc dò tên mình trong phạm vi bản chữ cái tên mình. Ví dụ, tên mình bắt đầu bằng chữ cái T, do đó mình chỉ việc tìm tên trong phạm vi chữ T. Tùy vào vị trí mình chọn mà mình sẽ dò tên mình theo hướng tiến hoặc lùi.

Trong lập trình, để tìm kiếm một phần tử trong mảng, danh sách. Cách tìm kiếm đơn giản nhất là tìm kiếm tuần tự, hay còn gọi là tìm kiếm lân cận (linear search). Ý tưởng rất đơn giản, ta chỉ việc kiểm tra lần lượt các phần tử từ đầu đến cuối để tìm phần tử thỏa điều kiện.

Ví dụ: Cho mảng gồm 16 số nguyên tố tăng dần: 2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 31, 37, 39 ,41, 43, 47

Để tìm vị trí số 13 trong mảng, ta cứ việc kiểm tra lần lượt phần tử đầu tiên là 2, cho đến hết mảng và trả về vị trí của số 13.

Trường hợp tổng quát, nếu may mắn, số ở vị trí đầu tiên là số cần tìm thì ta chỉ cần 1 lần kiểm tra. Tuy nhiên, nếu số cần tìm ở vị trí cuối cùng hoặc không có trong mảng, ta sẽ phải thực hiện kiểm tra đến 16 lần.

Vì là mảng các số nguyên tăng dần nên trong trường hợp này ta có thể dùng thuật toán tìm nhị phân . Cách thực hiện rất đơn giản, đầu tiên ta kiểm tra số chính giữa mảng có phải là số cần tìm hay không, nếu không ta có thể loại bỏ 1/2 số phần tử và tiếp tục tìm kiếm trong 1/2 còn lại. Cứ mỗi lần chọn phần tử để so sánh, ta sẽ loại bỏ được 1/2 số phần tử không phù hợp. Ở ví dụ trên, việc tìm kiếm nhị phân sẽ được thực hiện như sau:

– Đầu tiên chọn phần tử để kiểm tra ở giữa mảng là 19, vì số cần tìm là 13 nhỏ hơn 19 nên ta loại bỏ được 1/2 phần tử từ 19 – 47 và chỉ cần tìm trong phạm vi từ 2 – 17.

– Lần tiếp theo tương tự ta chọn số 7, vì 7 nhỏ hơn 13 nên ta cũng loại bỏ được 1/2 số phần tử và tiếp tục tìm trong phạm vi từ 11 – 17.

– Lần cuối cùng ta chọn 13 để so sánh, lần này ta trả về kết quả cần tìm.

Trong cách tìm kiếm nhị phân, rõ ràng, số lần chúng ta kiểm tra sẽ ít hơn rất nhiều so với tìm kiếm tuần tự, trong trường hợp trên, trường hợp xấu nhất ta cũng mất tối đa là 5 lần để kiểm tra.

Đặc biệt, vì mỗi lần chọn số cần tìm là lại loại bỏ được 1/2 phần tử, nên khi số lượng phần tử cần tìm tăng lên gấp đôi, ta chỉ mất thêm 1 lần để kiểm tra. Số lần cần kiếm tra trong thuật toán tìm kiếm nhị phân sẽ là logarit cơ số 2 của n. Để xem mức độ hiệu quả của thuật toán tìm kiếm nhị phân, ta có thể xem bảng logn:

Thử tưởng tượng, nếu bạn cần tìm user theo id, trong danh sách (list) user được sắp xếp id tăng dần lên đến xấp xỉ 1000 phần tử, chúng ta chỉ mất tối đa 11 lần so sánh để tìm ra kết quả. Một sự cải thiện đáng kinh ngạc so với 1000 lần kiếm tra (trường hợp xấu nhất) theo thuật toán tìm kiếm tuần tự!

Giải thuật

Giải thuật của tìm kiếm nhị phân rất đơn giản, như phần ví dụ ở trên, mình chỉ cần thực hiện bằng các bước.

1. Chọn min là 0 và max = n -1 (n là số phần tử của mảng)

2. Nếu max nhỏ hơn min, số cần tìm không tồn tại, trả về -1

3. Chọn mid là số chính giữa mảng

4. Nếu mid là số cần tìm (target), ta trả về giá trị cần tìm

5.  Nếu mid < target, ta set lại min = mid + 1

6. Nếu mid > target, ta set lại max = mid – 1;

7. Lập tại bước 2

Code

Có nhiều cách để implement tìm kiếm nhị phân, nhưng thường thì mình dùng vòng lặp while

package binarysearch;
 
/**
 *
 * @author thachlp
 */
public class BinarySearch {
 
    private static int binarySearch(int arr[], int target) {
        int min = 0;
        int max = arr.length - 1;
        int mid = 0;
 
        while (min <= max) {
            mid = (min + max) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
 
        return -1;
    }
 
    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 31, 37, 39 ,41, 43, 47};
        System.out.println("Found 13 at index: " + binarySearch(arr, 13));
    }
 
}

Đoạn code trên là ví dụ minh họa với các phần tử là số nguyên, nhưng chúng ta cũng có thể vận dụng cho các trường hợp các giá trị của phần tử là chữ cái, số… miễn là chúng được sắp xếp tăng dần. (Chúng ta cũng có thể tối ưu danh sách trước khi tìm kiếm bằng cách sort object, xem thêm tại đây)

Kết

Qua bài viết của mình, hy vọng các bạn đã cảm thấy được sự hiệu quả của thuật toán tìm kiếm nhị phân, qua đó có thể tự tin vận dụng vào dự án của mình đạt hiệu quả cao nhất. Các bài sau, mình sẽ tiếp tục giới thiệu đến các giải thuật khác. Cảm ơn các bạn đã đọc và hẹn gặp lại.

3 thoughts on “Tìm kiếm nhị phân | Binary search

Tham gia bình luận