Binary Search Algorithm
1. Đặt vấn đề
Cho 1 mảng các số nguyên n phần tử, đã được sắp xếp, tìm vị trí của giá trị nào đó bất kì trong mảng
ví dụ: cho mảng số nguyên 10 phần tử nằm trong khoảng -20 đến 20, tìm vị trí của giá trị 5
Có 2 cách để xử lí bài toán này là linear search và binary search
- Linear search sẽ lặp qua từng phần tử trong mảng đến khi tìm được giá trị, độ phức tạp thời gian là O(n)
- Binary search có độ phức tạp thời gian là O(log(2) n) => Cách này tối ưu hơn, nhanh hơn
2. Binary search hoạt động như thế nào?
- Gọi L là giá trị đầu tiên của mảng, R là giá trị cuối cùng của mảng, M là giá trị tại vị trí chính giữa L và R
- Ta thấy M(1) < target(5) nên target nằm trong khoảng từ 1 đến 17, tiếp tục set L và M đến vị trị mới
- target lúc này nằm trong khoảng 2-9, ta chuyển R đến vị trí mới
- Như vậy là ta đã tìm được target sau 3 bước, nếu sử dụng linear phải mất 7 bước
- Nếu target không tồn tại trong mảng, mất 3 bước để tìm kiếm trong khi linear mất 10 bước để tìm đến vị trí cuối cùng của mảng
3. Time Complexity
- Ta thấy số phần tử tìm kiếm thay đổi 10 -> 5 -> 2
- Nếu ban đầu có n phần tử thì số phần tử thay đổi sẽ có dạng khái quát như sau
- Ta sẽ tốn khoảng x+1 = log(2)n + 1 ≈ log(2)n bước để tìm ra target. Nếu mảng có 10.000.000 phần tử thì chỉ mất khoảng 24 bước để tìm ra target. Woa!!!!
4. Demo (Ruby language)
1 2 3 4 5 6 7 8 9 10 11 12 | <span class="token keyword">def</span> <span class="token method-definition"><span class="token function">search</span></span> arr<span class="token punctuation">,</span> target left <span class="token operator">=</span> <span class="token number">0</span> right <span class="token operator">=</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span> <span class="token keyword">while</span> left <span class="token operator"><=</span> right mid <span class="token operator">=</span> <span class="token punctuation">(</span>left <span class="token operator">+</span> right<span class="token punctuation">)</span> <span class="token operator">/</span><span class="token number">2</span> <span class="token keyword">return</span> mid <span class="token keyword">if</span> arr<span class="token punctuation">[</span>mid<span class="token punctuation">]</span> <span class="token operator">==</span> target left <span class="token operator">=</span> mid <span class="token operator">+</span> <span class="token number">1</span> <span class="token keyword">if</span> target <span class="token operator">></span> arr<span class="token punctuation">[</span>mid<span class="token punctuation">]</span> right <span class="token operator">=</span> mid <span class="token operator">-</span> <span class="token number">1</span> <span class="token keyword">if</span> target <span class="token operator"><</span> arr<span class="token punctuation">[</span>mid<span class="token punctuation">]</span> <span class="token keyword">end</span> <span class="token keyword">end</span> |