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:
- 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.
- Nếu
K=XK = X, chứng tỏ midmidlà vị 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,mid−1][left, mid – 1]
xem còn vị trí nào bằng XX
nữa không).
- Nếu
K>XK gt X, chứng tỏ XXnếu có tồn tại trong dãy số, nó sẽ ở vị trí từ [left,mid−1][left, mid – 1]
(phía trái dãy số).
- Nếu
K<XK lt X, chưng tỏ XXnế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ố).
- 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ị:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | <span class="token keyword">int</span> <span class="token function">binarySearch</span><span class="token punctuation">(</span><span class="token keyword">int</span> <span class="token operator">*</span>arr<span class="token punctuation">,</span> <span class="token keyword">int</span> X<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">int</span> result <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">int</span> l <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> r <span class="token operator">=</span> sz <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">int</span> mid<span class="token punctuation">;</span> <span class="token keyword">while</span> <span class="token punctuation">(</span>l <span class="token operator"><=</span> r<span class="token punctuation">)</span> <span class="token punctuation">{</span> mid <span class="token operator">=</span> <span class="token punctuation">(</span>l <span class="token operator">+</span> r<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">;</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>X <span class="token operator"><=</span> arr<span class="token punctuation">[</span>mid<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>arr<span class="token punctuation">[</span>mid<span class="token punctuation">]</span> <span class="token operator">==</span> X<span class="token punctuation">)</span> result <span class="token operator">=</span> mid<span class="token punctuation">;</span> r <span class="token operator">=</span> mid <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> l <span class="token operator">=</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> result<span class="token punctuation">;</span> <span class="token punctuation">}</span> |
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.