Idea:

Tìm một phần tử trong mảng đã được sắp xếp (sorted) bằng cách chia đôi mỗi lần tìm.

Luôn so sánh giá trị giữa (mid) với target để quyết định tìm bên trái hoặc phải.

🔹 Code:

def binarySearch(arr, target):
    L, R = 0, len(arr) - 1

    while L <= R:
        mid = (L + R) // 2

        if target > arr[mid]:
            L = mid + 1   # tìm bên phải
        elif target < arr[mid]:
            R = mid - 1   # tìm bên trái
        else:
            return mid    # tìm thấy
    return -1             # không tồn tại

🔹 Example:

arr = [1, 3, 5, 7, 9]
print(binarySearch(arr, 5))  # Output: 2
print(binarySearch(arr, 8))  # Output: -1

Giải thích:

• Mảng có index: [0, 1, 2, 3, 4] tương ứng [1, 3, 5, 7, 9]
• 5 nằm ở index 2 → trả về 2
• 8 không có → trả về 1

🔹 Key points:

• Chỉ hoạt động với sorted array
• Complexity:
  • Time: O(log n)
  • Space: O(1) (iterative) hoặc O(log n) (recursive)