thuật toán tìm kiếm nhị phân là gì ? Trình bày các bước mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên ?

Thuật toán tìm kiếm nhị phân (Binary Search) là một phương pháp tìm kiếm hiệu quả trong một mảng đã được sắp xếp. Thuật toán này hoạt động bằng cách chia đôi mảng và so sánh giá trị cần tìm với phần tử ở giữa mảng, từ đó quyết định tiếp tục tìm kiếm trong nửa mảng nào. Dưới đây là các bước mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên: 1. **Khởi tạo các biến**: Đặt hai biến `left` và `right` để đánh dấu chỉ số bắt đầu và kết thúc của mảng. `left` sẽ bằng 0 (chỉ số đầu tiên của mảng) và `right` sẽ bằng độ dài của mảng trừ 1 (chỉ số cuối cùng của mảng). 2. **Lặp lại cho đến khi `left` lớn hơn `right`**: - Tính chỉ số giữa `mid` bằng công thức: `mid = (left + right) / 2`. - So sánh giá trị tại chỉ số `mid` với giá trị cần tìm: - Nếu giá trị tại `mid` bằng giá trị cần tìm, thuật toán đã tìm thấy giá trị và có thể trả về chỉ số `mid`. - Nếu giá trị tại `mid` lớn hơn giá trị cần tìm, điều này có nghĩa là giá trị cần tìm nằm ở nửa bên trái của mảng. Do đó, cập nhật `right` bằng `mid - 1`. - Nếu giá trị tại `mid` nhỏ hơn giá trị cần tìm, điều này có nghĩa là giá trị cần tìm nằm ở nửa bên phải của mảng. Do đó, cập nhật `left` bằng `mid + 1`. 3. **Kết thúc**: Nếu vòng lặp kết thúc mà không tìm thấy giá trị cần tìm (tức là `left` lớn hơn `right`), thuật toán sẽ trả về một giá trị chỉ ra rằng giá trị không có trong mảng (thường là -1 hoặc một giá trị đặc biệt khác). Thuật toán tìm kiếm nhị phân có độ phức tạp thời gian là O(log n), làm cho nó rất hiệu quả cho các mảng lớn.