Thuật toán tìm kiếm nhị phân là một thuật toán tìm kiếm hiệu quả được sử dụng để định vị một mục cụ thể trong danh sách được sắp xếp trong một giới hạn thời gian nhất định. Nó còn được gọi là tìm kiếm nửa khoảng, tìm kiếm logarit hoặc cắt nhị phân. Tìm kiếm nhị phân hoạt động bằng cách so sánh giá trị đích với phần tử ở giữa của mảng. Nếu phần nhỏ bằng nhau thì chỉ số của phần tử ở giữa được trả về. Nếu mục tiêu nhỏ hơn phần tử ở giữa, thuật toán tiếp tục tìm kiếm ở phần dưới của mảng. Tương tự, nếu giá trị đích lớn hơn phần tử ở giữa, thuật toán sẽ tìm kiếm ở phần trên của mảng. Quá trình này tiếp tục cho đến khi tìm được mục hoặc cho đến khi toàn bộ mảng được tìm kiếm.
Độ phức tạp về thời gian của tìm kiếm nhị phân là O(log n), trong đó n là số phần tử trong mảng. Điều này làm cho nó trở thành một thuật toán hiệu quả so với tìm kiếm tuyến tính, vốn có độ phức tạp về thời gian là O(n). Điều quan trọng cần lưu ý là tìm kiếm nhị phân chỉ hoạt động trên danh sách được sắp xếp, vì bất kỳ sự khác biệt nào về thứ tự các phần tử đều có thể dẫn đến thuật toán không hoạt động đúng.
Tìm kiếm nhị phân có thể được sử dụng để tìm kiếm thông qua cơ sở dữ liệu, từ điển và mảng lớn. Nó cũng được sử dụng trong trình biên dịch và trình thông dịch để phân tích cú pháp và tối ưu hóa mã. Tìm kiếm nhị phân là một trong những thuật toán cơ bản của khoa học máy tính và được dạy trong các lớp lập trình cơ bản.
