"Chia để trị" (Divide and Conquer) là một trong những tư duy thiết kế giải thuật quan trọng nhất trong Tin học. Tư duy này gồm 3 bước:

1. Chia (Divide): Chia bài toán kích thước $N$ thành các bài toán con nhỏ hơn cùng dạng. (Trong Binary Search: Chia mảng thành 2 nửa tại vị trí mid).

2. Trị (Conquer): Giải quyết bài toán con. (So sánh $X$ với arr[mid] để quyết định loại bỏ hẳn 50% dữ liệu và chỉ giải quyết 1 nửa còn lại).

3. Kết hợp (Combine): Tổng hợp kết quả từ bài toán con để ra đáp án bài toán lớn.

Cài đặt Binary Search Chuẩn xác trong Python

def binary_search(arr: list, target: int) -> int:
    left, right = 0, len(arr) - 1

    while left <= right:
        # Tránh tràn số (Overflow) trong một số ngôn ngữ như C++/Java:
        # mid = left + (right - left) // 2
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid  # Trả về vị trí index
        elif arr[mid] < target:
            left = mid + 1  # Tìm ở nửa bên phải
        else:
            right = mid - 1  # Tìm ở nửa bên trái

    return -1  # Không tìm thấy target


# Demo
data = [12, 23, 34, 45, 56, 67, 78, 89]
print(binary_search(data, 56))  # Output: 4
print(binary_search(data, 99))  # Output: -1