Tìm kiếm (Searching)

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 5)

Tìm kiếm (Searching)

Binary Search

Thời gian (Time) O(log n)
Không gian (Space) O(1)

Mô tả nguyên lý

Tìm kiếm trên mảng đã sắp xếp bằng cách chia đôi khoảng giá trị ở mỗi bước.

Cài đặt mẫu (Implementation)

function binarySearch($arr, $target) {
    $l = 0; $r = count($arr) - 1;
    while ($l <= $r) {
        $m = floor(($l + $r) / 2);
        if ($arr[$m] == $target) return $m;
        if ($arr[$m] < $target) $l = $m + 1;
        else $r = $m - 1;
    }
    return -1;
}
Tìm kiếm (Searching)

Exponential Search

Thời gian (Time) O(log n)
Không gian (Space) O(1)

Mô tả nguyên lý

Tìm khoảng chứa phần tử bằng cách tăng lũy thừa 2, sau đó thực hiện tìm kiếm nhị phân.

Cài đặt mẫu (Implementation)

function exponentialSearch($arr, $target) {
    $n = count($arr);
    if ($n == 0) return -1;
    if ($arr[0] == $target) return 0;
    $i = 1;
    while ($i < $n && $arr[$i] <= $target) $i = $i * 2;
    return binarySearchRange($arr, $i / 2, min($i, $n - 1), $target);
}
Tìm kiếm (Searching)

Interpolation Search

Thời gian (Time) O(log log n)
Không gian (Space) O(1)

Mô tả nguyên lý

Cải tiến của tìm kiếm nhị phân, ước lượng vị trí dựa trên giá trị của phần tử cần tìm.

Cài đặt mẫu (Implementation)

function interpolationSearch($arr, $target) {
    $low = 0; $high = count($arr) - 1;
    while ($low <= $high && $target >= $arr[$low] && $target <= $arr[$high]) {
        if ($low == $high) {
            if ($arr[$low] == $target) return $low;
            return -1;
        }
        $pos = $low + floor((($high - $low) / ($arr[$high] - $arr[$low])) * ($target - $arr[$low]));
        if ($arr[$pos] == $target) return $pos;
        if ($arr[$pos] < $target) $low = $pos + 1;
        else $high = $pos - 1;
    }
    return -1;
}
Tìm kiếm (Searching)

Jump Search

Thời gian (Time) O(√n)
Không gian (Space) O(1)

Mô tả nguyên lý

Tìm kiếm trên mảng đã sắp xếp bằng cách nhảy qua các bước có kích thước cố định trước khi tìm kiếm tuyến tính.

Cài đặt mẫu (Implementation)

function jumpSearch($arr, $target) {
    $n = count($arr);
    $step = sqrt($n);
    $prev = 0;
    while ($arr[min($step, $n) - 1] < $target) {
        $prev = $step;
        $step += sqrt($n);
        if ($prev >= $n) return -1;
    }
    while ($arr[$prev] < $target) {
        $prev++;
        if ($prev == min($step, $n)) return -1;
    }
    if ($arr[$prev] == $target) return $prev;
    return -1;
}
Tìm kiếm (Searching)

Linear Search

Thời gian (Time) O(n)
Không gian (Space) O(1)

Mô tả nguyên lý

Duyệt tuần tự từng phần tử trong mảng từ đầu đến cuối để tìm giá trị mục tiêu.

Cài đặt mẫu (Implementation)

function linearSearch($arr, $target) {
    foreach ($arr as $i => $val) {
        if ($val == $target) return $i;
    }
    return -1;
}