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)

def search arr, target
    left = 0
    right = arr.length - 1
    while left <= right
        mid = (left + right) /2
        return mid if arr[mid] == target

        left = mid + 1 if target > arr[mid]
        right = mid - 1 if target < arr[mid]
    end
end