close

Thuật toán Tìm kiếm Nhị phân (Binary Search) trong PHP: Giải thích, Bước thực hiện và Ví dụ

Thuật toán Tìm kiếm Nhị phân là một phương pháp hiệu quả để tìm kiếm một giá trị cụ thể trong một mảng đã được sắp xếp. Phương pháp này chia mảng thành các phần nhỏ hơn và liên tục so sánh giá trị tại vị trí giữa của khoảng tìm kiếm với giá trị cần tìm. Nếu giá trị khớp, ta đã tìm thấy giá trị; nếu không, ta tiếp tục chia nhỏ khoảng tìm kiếm và lặp lại quá trình cho đến khi tìm thấy hoặc không còn phần tử nào để kiểm tra.

Steps to take

  1. Khởi tạo khoảng tìm kiếm: Ban đầu, chọn khoảng tìm kiếm từ vị trí đầu left đến vị trí cuối right của mảng.
  2. Tìm điểm giữa: Tính toán điểm giữa bằng cách lấy trung bình của vị trí left và right, đây chính là điểm giữa của khoảng tìm kiếm.
  3. So sánh giá trị: So sánh giá trị tại điểm giữa với giá trị cần tìm.
  4. Xử lý kết quả so sánh: Nếu giá trị tại điểm giữa bằng giá trị cần tìm, trả về vị trí này. Nếu giá trị tại điểm giữa nhỏ hơn giá trị cần tìm, thay đổi vị trí left thành giữa + 1 để tìm trong nửa phía sau. Nếu giá trị tại điểm giữa lớn hơn giá trị cần tìm, thay đổi vị trí right thành giữa - 1 để tìm trong nửa phía trước.
  5. Lặp lại: Lặp lại bước 2 đến 4 cho đến khi tìm thấy giá trị hoặc không còn phần tử để kiểm tra (left > right).

Ưu nhược điểm của thuật toán

Ưu điểm:

  • Hiệu suất tốt: Độ phức tạp thời gian của thuật toán là O(log n), làm cho nó rất hiệu quả khi xử lý dãy dữ liệu lớn.
  • Hiệu quả cho dãy dữ liệu lớn: Khi dãy dữ liệu lớn, Tìm kiếm Nhị phân giúp giảm số lượng phần tử cần kiểm tra nhanh chóng.

Nhược điểm:

  • Chỉ áp dụng cho mảng đã sắp xếp: Thuật toán chỉ hoạt động trên dãy đã được sắp xếp.
  • Số bước không cố định: Số bước cần để tìm thấy giá trị phụ thuộc vào vị trí của giá trị trong mảng, có thể tốn nhiều bước ở những vị trí gần cuối dãy.

Ví dụ: Tìm kiếm số 12 trong mảng sắp xếp bằng Tìm kiếm Nhị phân

function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);

        if ($arr[$mid] == $target) {
            return $mid; // Trả về vị trí của giá trị
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }

    return -1; // Không tìm thấy giá trị
}

$array = [2, 5, 8, 12, 15, 20, 30];
$targetValue = 12;

$result = binarySearch($array, $targetValue);

if ($result != -1) {
    echo "Giá trị $targetValue được tìm thấy tại vị trí $result.";
} else {
    echo "Không tìm thấy giá trị $targetValue trong mảng.";
}

Giải thích ví dụ

  1. Ta bắt đầu với khoảng tìm kiếm ban đầu từ vị trí đầu (left = 0) đến vị trí cuối (right = 6) của mảng.
  2. Ta tính toán điểm giữa (mid) bằng cách lấy trung bình của left và right, nên mid = 3. Giá trị tại mid là 12.
  3. Ta so sánh giá trị tại mid (12) với giá trị cần tìm (12) và thấy chúng khớp, nên ta trả về vị trí 3.
  4. Thuật toán kết thúc và xuất kết quả "Giá trị 12 được tìm thấy tại vị trí 3."