Binary Search
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;
}
Exponential Search
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);
}
Interpolation Search
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;
}
Jump Search
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;
}
Linear Search
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;
}