- vừa được xem lúc

Binary Search - Tìm kiếm nhị phân

0 0 10

Người đăng: Hạnh

Theo Viblo Asia

Chào các bạn!

Tiếp theo chuỗi series về các thuật toán sắp xếp và tìm kiếm căn bản, thì ở bài viết này mình sẽ trình bày các bạn phần thuật toán tìm kiếm nhị phân.

Ở bài trước thì chúng ta đã cùng tìm hiểu thuật toán tìm kiếm tuần tự, và nó thực sự là thuật toán đơn giản và chậm chạp nhất, nhưng nó thực sự là giải pháp được lựa chọn nhiều nhất bởi nó có thể giải quyết mọi bài toán tìm kiếm.

Tuy nhiên, với một trường hợp dãy số đã có thứ tự cho sẵn, thì việc duyệt từ đầu đến cuối dãy số là điều vô nghĩa, vì ta có thể lựa chọn cách duyệt khôn ngoan hơn. Như mình sẽ trình bày dưới đây.


Đặt vấn đề

Cho dãy số sắp xếp tăng dần có kích thước NN phần tử và số XX. Hãy xác định vị trí đầu tiên mà XX xuất hiện trong dãy số.

Ý tưởng thuật toán

Lần này, chúng ta sẽ không duyệt qua toàn bộ dãy số nữa, mà chúng ta sẽ làm theo các bước sau:

  1. Xác định vị trí chính giữa của dãy số, gọi giá trị này là KK và vị trí chính giữa này là: midmid.
  2. Nếu K=XK = X, chứng tỏ midmidvị trí cần tìm (tuy nhiên, do yêu cầu xác định vị trí đầu tiên mà XX xuất hiện, nên ta vẫn phải tìm kiếm trong đoạn [left,mid1][left, mid - 1] xem còn vị trí nào bằng XX nữa không).
  3. Nếu K>XK \gt X, chứng tỏ XX nếu có tồn tại trong dãy số, nó sẽ ở vị trí từ [left,mid1][left, mid - 1] (phía trái dãy số).
  4. Nếu K<XK \lt X, chưng tỏ XX nếu có tồn tại trong dãy số, nó sẽ ở vị trí từ [mid+1,right][mid + 1, right] (phía phải dãy số).
  5. Gọi lại bước tìm kiếm ứng với vị trí mà XX có thể tồn tại.

Lưu ý: Vốn dĩ ta có thể phân đôi tìm kiếm như trên được là do dãy số đã có thứ tự tăng dần, nếu dãy số không có thứ tự, bạn không thể nào tìm kiếm bằng cách này được! Mà phải nghĩ đến cách khác.

Và dưới đây là code mà mình đã chuẩn bị:

int binarySearch(int *arr, int X) { int result = -1; int l = 0, r = sz - 1; int mid; while (l <= r) { mid = (l + r) / 2; if (X <= arr[mid]) { if (arr[mid] == X) result = mid; r = mid - 1; } else { l = mid + 1; } } return result;
}

Full code bạn có thể xem ở đây: https://ideone.com/bebfos

Đánh giá độ phức tạp

Dễ thấy rằng, độ phức tạp của giải thuật trên là O(logN)O(logN), bởi vì mỗi bước tìm kiếm, ta lại chia đôi dãy số ra làm 2. Điều này làm nó tìm kiếm nhanh hơn một cách bất ngờ.

Và nếu bạn nhấn vào link full code ở phía trên, bạn sẽ tìm thấy dòng này ở stdout

Total time for search: 0(s)

Trong đoạn code trên, mình đã cho tìm kiếm giá trị XX tới 10.00010.000 lần, kết quả lại vẫn là tìm kiếm trong 0s. Trong khi mình chỉ mới tìm kiếm 10001000 lần ở tìm kiếm tuần tự, lại cho ra tới 3s.

Kết luận

Trên đây, mình đã trình bày các bạn về thuật toán Binary Search. Thuật toán này thực sự đơn giản, tuy nhiên lại vô cùng hiểu quả với các bài toán đặc thù là đã dãy số đã có thứ tự (bất kể tăng hay giảm đều sử dụng được).

Bạn hãy thuộc làu làu nó để tận dung ngay lúc có thể nhé.

Nếu bạn có bất cứ ý kiến nào đóng góp, xin hãy gửi comment, mình sẽ trả lời và khắc phục cho những lần sau.

Bình luận

Bài viết tương tự

- vừa được xem lúc

Các thuật toán cơ bản trong AI - Phân biệt Best First Search và Uniform Cost Search (UCS)

Nếu bạn từng đọc các thuật toán trong AI (Artificial Intelligence - Trí tuệ nhân tạo), rất có thể bạn từng nghe qua về các thuật toán tìm kiếm cơ bản: UCS (thuộc chiến lược tìm kiếm mù) và Best First Search (thuộc chiến lược tìm kiếm kinh nghiệm). Khác nhau rõ từ khâu phân loại rồi, thế nhưng hai th

0 0 152

- vừa được xem lúc

NodeJS Bài 4: Query Parameters

Series NodeJS căn bản cho người mới bắt đầu. . . Xem bài viết mới - ReactJS -Những câu hỏi phỏng vấn thường gặp - Phần 1.

0 0 32

- vừa được xem lúc

Cải thiện Tìm kiếm trong Database Full-text search

Mục tiêu: Cải thiện tìm kiếm trong database (DB) hay nói cách khác là làm sao để tìm kiếm trong database cho nó thông minh hơn. Giới thiệu.

0 0 18

- vừa được xem lúc

Học lập trình game cần những gì?

Lập trình game là làm gì. Các ngôn ngữ các bạn có thể sử dụng để lập trình game : C, C++, C#, Java, Python,... Các bước cơ bản để lập trình game. . Hiển thị: Đã là game thì hiển thị không thể thiếu, lúc đầu các bạn chỉ làm cho phần hiển thị thật đơn giản, các bạn đừng quá chú tâm vào việc làm sao ch

0 0 32

- vừa được xem lúc

[MFC] Http request with winsock2.h

Giới thiệu. Xin chào, trong bài này mình sẽ giới thiệu 1 số lưu ý khi sử dụng thư viện winsock2.h (thư viện window socket) sử dụng trong window app. Đầu tiên, bạn sẽ dễ dàng search được 1 ví dụ cụ thể trên document của winsock2.

0 0 20

- vừa được xem lúc

Design parttern

Builder. 1. Ý tưởng. Builder là một mẫu thiết kế sáng tạo cho phép bạn xây dựng các đối tượng phức tạp theo từng bước.

0 0 22