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

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 $N$ phần tử và số $X$. Hãy xác định vị trí đầu tiên mà $X$ 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à $K$ và vị trí chính giữa này là: $mid$.
2. Nếu $K = X$, chứng tỏ $mid$ là vị trí cần tìm (tuy nhiên, do yêu cầu xác định vị trí đầu tiên mà $X$ xuất hiện, nên ta vẫn phải tìm kiếm trong đoạn $[left, mid - 1]$ xem còn vị trí nào bằng $X$ nữa không).
3. Nếu $K \gt X$, chứng tỏ $X$ nếu có tồn tại trong dãy số, nó sẽ ở vị trí từ $[left, mid - 1]$ (phía trái dãy số).
4. Nếu $K \lt X$, chưng tỏ $X$ nếu có tồn tại trong dãy số, nó sẽ ở vị trí từ $[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à $X$ 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)$, 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ị $X$ tới $10.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 $1000$ 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.