Bài 50. Thuật toán tìm kiếm nhị phân

Bài số 48 trong 69 bài của series Học C Không Khó

Thuật toán tìm kiếm nhị phân là một trong các thuật toán sắp xếp được sử dụng rất nhiều trong thực tế. Hãy cùng mình đi tìm hiểu thuật toán tìm kiếm này nhé.

Tìm kiếm là một phần không thể thiếu của mọi ứng dụng, website hay phần mềm. Tính năng tìm kiếm cho phép người sử dụng nhanh chóng truy vấn và tìm kiếm các bản ghi theo mong muốn. Và một công cụ tìm kiếm nổi tiếng nhất hàng ngày chúng ta vẫn thường sử dụng đó là Google search.

Bài viết ngày hôm nay Nguyễn Văn Hiếu sẽ giới thiệu cho độc giả một thuật toán tìm kiếm tối ưu áp dụng đối với trường hợp dữ liệu số đã sắp xếp.

Đối với các giải thuật sắp xếp, các bạn có thể đọc thêm tại: series các thuật toán sắp xếp

Phát biểu thuật toán tìm kiếm nhị phân(Binary search)

Cho một mảng đã sắp xếp arr[] có n phần tử, viết một hàm tìm kiếm trả về chỉ số của phần tử có giá trị x trong arr[].

Giải thuật đơn giản nhất cho bài toán này là sử dụng linear search(tìm kiếm tuyến tính). Tức là bạn sẽ phải đi qua từng phần tử của mảng để đối chiếu với x cần tìm. Thuật toán này trong trường hợp xấu nhất cho độ phức tạp là O(n). Mình cũng sẽ minh họa code của thuật toán này dưới đây.

Đây là code C/C++ sử dụng linear search.

Ý tưởng của thuật toán tìm kiếm nhị phân

Chú ý: Trong bài viết tôi giả sử mảng đang sắp xếp tăng dần. Với trường hợp mảng sắp xếp giảm dần, bạn đọc sau khi hiểu thuật toán sẽ có thể tự làm.

Do tính chất mảng đã sắp xếp, công việc tìm kiếm phần tử x có thể triển khai như sau:

  1. Xét đoạn mảng arr[left…right] cần tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:
  2. Nếu phần tử arr[mid] = x. Kết luận và thoát chương trình.
  3. Nếu arr[mid] < x. Chỉ thực hiện tìm kiếm trên đoạn arr[mid+1…right].
  4. Nếu arr[mid] > x. Chỉ thực hiện tìm kiếm trên đoạn arr[left…mid-1].

Hình ảnh dưới đây mô phỏng quá trình thực hiện của thuật toán tìm kiếm nhị phân và so sánh với thuật toán tìm kiếm tuyến tính.

So sánh thuật toán tìm kiếm nhị phân và tìm kiếm tuyến tính
So sánh thuật toán tìm kiếm nhị phân và tìm kiếm tuyến tính

Bằng cách áp dụng thuật toán tìm kiếm nhị phân, độ phức tạp cho trường hợp xấu nhất là O(log(n)).

Minh họa code cho thuật toán tìm kiếm nhị phân

Trong phần này, mình sẽ minh họa code sử dụng giải thuật đệ quy dùng Java và C/C++. Ngoài ra, tôi sẽ áp dụng thêm giải thuật khử đệ quy với C/C++.

Code minh họa C/C++ sử dụng đệ quy

Code minh họa sử dụng đệ quy Java

Code khử đệ quy sử dụng C/C++

Các bài viết trong SeriesBài trước: Bài 49. Thuật toán sắp xếp chèn (Insertion sort)Bài sau: Bài 51. Tìm số lớn thứ 2 trong mảng

27 BÌNH LUẬN

    • Bạn đã có chỉ số của phần tử cần tìm trong mảng rồi, hãy kiểm tra các phần tử lân cận xem có bằng phần tử tìm được không là được mà. Mình có thể làm được điều này là vì mảng đã sắp xếp rồi.

    • C1: Giả sử nếu l là một số rất lớn(r mặc nhiên lớn hơn l rồi), khi cộng giá trị thu được sẽ >= 2*l và sau đó mới chia 2.

      C2: Nếu bạn dùng l + (r-l)/2 thì chúng ta không cần lưu một giá trị lớn gấp đôi l mà chỉ cộng 1/2 lượng chênh lệch của r và l vào biến l.

      Cả 2 cách đều cho ra 1 kết quả, nhưng rõ ràng dùng cách thứ 2 sẽ tối ưu hơn. Khả năng tràn số của cách 1 là cao hơn hẳn, mục tiêu của chúng ta là tối ưu hơn thôi chứ trường hợp tràn số chắc ít xảy ra lắm.

  1. Anh cho em hỏi. Giả sử em có mảng đã được sắp xếp {1, 1, 1, 1, 3}. Em tìm được phần tử ở vị trí giữa là 1 bằng với x. Rồi em kiểm tra left nếu bằng x thì in ra vị trí từ left đến mid. Sau đó em câp nhật lại left để xét các số phía sau. Vậy có đảm bảo tính chất của thuật toán nhị phâm ko ạ? Xin cảm ơn.

    • Thuật toán tìm kiếm nhị phân kết thúc khi em tìm được phần tử em muốn tìm. Các bước xử lý sau đó của em không còn liên quan gì tới tìm kiếm nhị phân nhé em.

      Về bài toán của em, nếu anh hiểu thì là em cần tìm và in ra vị trí của tất cả các số trong mảng có giá trị = x => cách em làm như vậy là tối ưu rồi. Em có thể sửa lại thuật toán tìm kiếm nhị phân để tìm ra phần tử đầu tiên bằng với x thay vì tìm ra 1 thằng ở giữa (tuy nhiên độ phức tạp không đổi).

  2. int binarySearch(int arr[], int n, int x)
    {
    int r = n – 1; // chỉ số phần tử cuối
    int l = 0; // Chỉ số phần tử đầu tiên
    while (r >= l)
    {
    int mid = l + (r – l) / 2; // Tương đương (l+r)/2 nhưng ưu điểm tránh tràn số khi l,r lớn

    // Nếu arr[mid] = x, trả về chỉ số và kết thúc.
    if (arr[mid] == x)
    return mid;

    // Nếu arr[mid] > x, cập nhật lại right
    if (arr[mid] > x)
    r = mid – 1;
    // Nếu arr[mid] > x, cập nhật lại left
    l = mid + 1;
    }

    // Nếu không tìm thấy
    return -1;
    }
    Đoạn l = mid+1 hình như phải if(arr[mid]<x) l = mid + 1; chứ ạ

  3. anh ơi cho em hỏi là sử dụng thuật toán tìm kiếm nhị phân thì bắt buộc dãy mình nhập vào phải là dãy đã được sắp xếp tăng dần ạ

    • Uh em, dãy sắp xếp rồi thì mới tìm kiếm nhanh được.

      Nếu dãy chưa sắp xếp thì nếu em sắp xếp rồi dùng thì cũng chậm hơn tìm kiếm tuyến tính nhé.

      Vì thuật toán sắp xếp nhanh nhất cũng phức tạp hơn thuật toán tìm kiếm tuyến tính rồi. Nhưng nếu em phải tìm kiếm nhiều lần thì ta lại nên sắp xếp để tìm kiếm nhị phân cho nhanh.

  4. anh ơi anh có thể giải thích giúp em toán tử sizeof được k ạ ,tại sao ko phải n=sizeof(arr) mà lại là n=sizeof(arr)/sizeof(arr[0]) vậy ạ,em cảm ơn.

  5. Cho em hỏi là ở dòng 25: Tại sao mình vừa thoát vòng lặp rồi, dù ko có điều kiện gì cả nhưng sao cái lệnh return -1 đó nó ko trả -1 về cho hàm ạ??

    • nếu thỏa mãn đk thì nó sẽ gặp lệnh return mid trong khối while và thoát hàm ngay lúc đó chứ k gặp được câu lệnh return -1 trong hàm

  6. anh ơi cho em hỏi tại sao phần khử đệ quy C/C++ có 2 chi tiết này không ạ?
    1, dòng 22 tại sao lại không có điều kiện?
    2, dòng 32 tại sao lại gán n như vậy ạ?

    • theo mình hiểu thì:
      1. ko cần điều kiện vì trong đó chỉ xảy ra 3 trường hợp ko vào 2 điều kiện trên thì chắc chắn vào cái còn lại.
      2. n là số phần tử của mảng.câu lệnh đó tìm ra số phần tử của mảng.bạn muốn hiểu chi tiết thì xem lại 2,3 bài trc đó ở phần bình luận a đã giải thích rất chi tiết đó.

  7. int main(void) {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n – 1, x);
    if (result == -1)
    printf(“%d xuat hien tai chi so %d”, x, result);
    else
    printf(“%d xuat hien tai chi so %d”, x, result);
    return 0;
    }
    Anh ơi, khúc result == -1, anh in nhầm nè anh

BÌNH LUẬN

Vui lòng nhập bình luận của bạn
Vui lòng nhập tên của bạn ở đây