1. Bản chất & Ràng buộc Dữ liệu

Tìm kiếm là thao tác xác định sự tồn tại hoặc vị trí (chỉ số) của một giá trị $X$ (key) trong tập dữ liệu $N$ phần tử.

1. Linear Search (Mảng bất kỳ - Không cần sắp xếp):
   [ 45 | 12 | 89 | 23 | 78 ]  --> Duyệt lần lượt từng ô: O(N)

2. Binary Search (Mảng ĐÃ SẮP XẾP):
   [ 12 | 23 | 45 | 78 | 89 ]  --> So sánh phần tử ở GIỮA: O(log N)
              ^
             MID

• Linear Search (Tìm kiếm tuyến tính):

  • Cách vận hành: Lần lượt so sánh $X$ với từng phần tử từ chỉ số $0$ đến $N-1$.

  • Ưu điểm: Áp dụng trên mọi cấu trúc dữ liệu (mảng, danh sách liên kết) và không yêu cầu dữ liệu phải sắp xếp.

  • Độ phức tạp: $O(N)$ thời gian, $O(1)$ bộ nhớ.

• Binary Search (Tìm kiếm nhị phân):

  • Ràng buộc duy nhất: Dữ liệu bắt buộc phải được sắp xếp theo thứ tự và hỗ trợ truy cập ngẫu nhiên $O(1)$ (như Mảng/List).

  • Cách vận hành:

    1. Xác định phạm vi tìm kiếm [left, right], tính vị trí giữa mid = (left + right) // 2.

    2. So sánh arr[mid] với $X$:

       • Nếu arr[mid] == X: Tìm thấy! Trả về mid.

       • Nếu arr[mid] < X: $X$ chắc chắn nằm ở nửa sau $\rightarrow$ Thu hẹp phạm vi: left = mid + 1.

       • Nếu arr[mid] > X: $X$ chắc chắn nằm ở nửa đầu $\rightarrow$ Thu hẹp phạm vi: right = mid - 1.

  • Độ phức tạp: $O(\log N)$ thời gian, $O(1)$ bộ nhớ (với cách cài đặt vòng lặp).