Categories Thuật toán

Tìm kiếm nhị phân [serial về các thuật toán cơ bản trong lập trình]

Tìm kiếm nhị phân

Tìm kiếm nhị phân (binary search) là một trong các thuật toán cơ bản trong lập trình mà chúng ta cũng cần phải biết. Ưu điểm của nó là tốc độ tốt (ví dụ khi so với tìm kiếm tuyến tính / tuần tự) trên các mảng có số lượng phần tử lớn, ngoài ra, tìm kiếm nhị phân cũng dễ hiểu nữa.

Một yêu cầu trong tìm kiếm nhị phân là mảng mà nó cần tìm kiếm cần phải được sắp xếp rồi (chẳng hạn bằng quick sort).

Ví dụ, hãy tìm vị trí của giá trị 75 trong mảng sau:

1, 3, 4, 7, 9, 32, 45, 57, 68, 75, 92, 101

Nếu trong tìm kiếm tuyến tính, nó sẽ duyệt qua tất cả phần tử của mảng, rồi so khớp xem phần tử đó có đúng là phần tử cần tìm kiếm không, sau đó trả về kết quả vị trí.

Tìm kiếm nhị phân hoạt động thông minh hơn, vì mảng đã được sắp xếp, nên nó chia đôi mảng ra thành 2 mảng nhỏ là A và B, rồi đem so sánh phần tử cần tìm kiếm với phần tử cuối của mảng A, nếu nó đúng bằng phần tử này thì đây là phần tử cần tìm, nếu nó nhỏ hơn thì phần tử cần tìm sẽ nằm trong mảng A, nếu nó lớn hơn thì phần tử cần tìm sẽ nằm trong mảng B.

Như vậy, thông qua một thao tác so sánh, nó đỡ được 1/2 công sức duyệt cả mảng, không gian tìm kiếm của nó thu hẹp rất nhanh, giúp quá trình này có tốc độ tốt. Quá trình phân đôi (nhị phân) này cứ tiếp tục cho đến khi nó tìm được vị trí chính xác.

Đoạn mã PHP để làm việc này:

function binary_search($arr, $x)
{
    $left = 0;
    $right = count($arr) - 1;
    while ($left <= $right) {
        $mid = intval(($left + $right) / 2); // lấy phần nguyên
        if($arr[$mid] == $x) { // nếu đúng bằng giá trị cần tìm
            return $mid; // ra được vị trí
            $left = $right + 1; // kết thúc
        }
        else if ($x < $arr[$mid]) {
// bỏ đi phần tử $arr[$mid], không phải so nữa, và thu hẹp vùng tìm kiếm
            $right = $mid - 1; 
        }
        else {
// bỏ đi phần tử $arr[$mid], không phải so nữa, và thu hẹp vùng tìm kiếm
            $left = $mid + 1;
        }
    }
// khi nó không tìm thấy
    return -1;
}

$arr = array(1, 3, 4, 7, 9, 32, 45, 57, 68, 75, 92, 101);
echo  binary_search($arr, 75); // kết quả là 9, là vị trí của phần tử 75 trong mảng

Quá trình này diễn tiến như sau:

Lần 1:

  • $left = 0, $right = 11, $mid = 5, $arr[5] = 32.
  • Mảng A1 = 1, 3, 4, 7, 9, 32
  • Mảng B1 = 45, 57, 68, 75, 92, 101
  • Vì 75 > 32, nên phần tử cần tìm nếu có chắc chắn không thuộc A1, do vậy nó tìm tiếp trong B1, với quá trình tương tự.
  • $left được cập nhật giá trị mới là $left = 5 + 1 = 6

Lần 2:

  • $left = 6, $right = 11, $mid = 8, $arr[8] = 68.
  • Mảng A2 = 45, 57, 68
  • Bảng B2 = 75, 92, 101
  • Vì 75 > 68, nên phần tử cần tìm nếu có chắc chắn không thuộc A2, do vậy nó tìm tiếp trong B2, với quá trình tương tự.
  • $left được cập nhật giá trị mới là $left = 8 + 1 = 9

Lần 3:

  • $left = 9, $right = 11, $mid = 10, $arr[10] = 92.
  • Mảng A3 = 75, 92
  • Mảng B3 = 101
  • Vì 75 < 92, nên phần tử cần tìm nếu có chắc chắn không thuộc B3, do vậy nó tìm tiếp trong A3, với quá trình tương tự.
  • $right được cập nhật là $right = 11 – 1 = 10

Lần 4:

  • $left = 9, $right = 10, $mid = 9, $arr[9] = 75.
  • Vì 75 = $arr[9], nó tìm được vị trí cần tìm, ở đây có giá trị là 9.

Một số lưu ý:

  • Tìm kiếm nhị phân chỉ hoạt động trên mảng đã sắp xếp, nên nếu mảng chưa sắp xếp, chúng ta cần sắp xếp lại nó trước khi dùng tìm kiếm nhị phân.
  • Trên các mảng có số lượng phần tử nhỏ, tìm kiếm tuyến tính có thể hiệu quả hơn.
  • Hiệu quả của tìm kiếm nhị phân là cao nhất khi sử dụng trên các mảng có số lượng phần tử lớn. Tuy mất thời gian phải sắp xếp lại phần tử lúc ban đầu, nhưng vì việc này chỉ phải làm một lần, trong khi đó thời gian tiết kiệm được khi thực hiện biện pháp tìm kiếm nhị phân là đáng kể và được tích lũy mỗi khi thực hiện.
Back to Top