Giới thiệu
Sau khi đã tìm hiểu về các chủ đề như toán tử, điều khiển luồng, hàm và sắp xếp mảng trong PHP, bài viết này sẽ trình bày về các kỹ thuật tìm kiếm cơ bản — một phần quan trọng trong xử lý dữ liệu. Hai phương pháp phổ biến được sử dụng là tìm kiếm tuần tự và tìm kiếm nhị phân, mỗi loại phù hợp với từng tình huống cụ thể.
Tìm kiếm tuần tự
Nguyên lý hoạt động: Duyệt lần lượt từng phần tử của mảng cho đến khi tìm thấy giá trị cần tìm. Phương pháp này đơn giản, dễ triển khai và không yêu cầu mảng phải được sắp xếp trước.
Ví dụ minh họa:
<?php
$mang = array(4, 3, 9, 1, 6, 23.5);
function timKiemTuanTu(&$mang, $giaTriCanTim) {
$timThay = false;
for ($i = 0; $i < count($mang); $i++) {
if ($mang[$i] == $giaTriCanTim) {
echo "Tìm thấy tại vị trí: $i";
$timThay = true;
break;
}
}
if (!$timThay) {
echo "Không tìm thấy giá trị trong mảng.";
}
}
timKiemTuanTu($mang, 9);
?>
Kết quả xuất ra: Tìm thấy tại vị trí: 2
Tìm kiếm nhị phân
Lưu ý quan trọng: Mảng phải được sắp xếp theo thứ tự tăng dần hoặc giảm dần trước khi áp dụng tìm kiếm nhị phân. Nếu không, kết quả trả về có thể sai.
Cơ chế: So sánh giá trị cần tìm với phần tử ở giữa mảng. Nếu nhỏ hơn, tiếp tục tìm ở nửa trái; nếu lớn hơn, tìm ở nửa phải; nếu bằng, trả về vị trí.
Phiên bản cải tiến với đệ quy:
<?php
$mangDaSapXep = array(1, 4, 6, 15, 18, 57);
function timNhiPhan(&$mang, $giaTri, $trai, $phai) {
if ($trai > $phai) {
echo "Không tìm thấy.";
return;
}
$giua = intval(($trai + $phai) / 2); // Làm tròn xuống
if ($giaTri > $mang[$giua]) {
timNhiPhan($mang, $giaTri, $giua + 1, $phai);
} elseif ($giaTri < $mang[$giua]) {
timNhiPhan($mang, $giaTri, $trai, $giua - 1);
} else {
echo "Tìm thấy tại chỉ số: $giua";
}
}
timNhiPhan($mangDaSapXep, 4, 0, count($mangDaSapXep) - 1);
echo "<br>";
print_r($mangDaSapXep);
?>
Kết quả:
Tìm thấy tại chỉ số: 1
Array ( [0] => 1 [1] => 4 [2] => 6 [3] => 15 [4] => 18 [5] => 57 )
Ứng dụng thực tế: Xử lý điểm số từ ban giám khảo
Yêu cầu: Người dùng nhập vào 6 điểm từ các giám khảo, hệ thống cần loại bỏ điểm cao nhất và thấp nhất, sau đó tính trung bình cộng của bốn điểm còn lại. Đồng thời, xác định và hiển thị thông tin giám khảo nào cho điểm cao nhất và thấp nhất.
Giao diện người dùng (HTML):
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Nhập điểm giám khảo</title>
</head>
<body>
<h1>Nhập điểm từ 6 giám khảo (cách nhau bởi dấu cách)</h1>
<form action="xulydiem.php" method="post">
<input type="text" name="diem" size="50" placeholder="Ví dụ: 88 90 60 78 100 93">
<input type="submit" value="Xử lý">
</form>
</body>
</html>
Xử lý dữ liệu phía server (xulydiem.php):
<?php
if ($_SERVER['REQUEST_METHOD'] == 'POST') {
$dauVao = trim($_POST['diem']);
$diemArr = explode(' ', $dauVao);
// Chuyển tất cả thành số thực
$diemArr = array_map('floatval', $diemArr);
// Tìm chỉ số điểm thấp nhất
function timChiSoThapNhat($arr) {
$minVal = $arr[0];
$index = 0;
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] < $minVal) {
$minVal = $arr[$i];
$index = $i;
}
}
return $index;
}
// Tìm chỉ số điểm cao nhất
function timChiSoCaoNhat($arr) {
$maxVal = $arr[0];
$index = 0;
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] > $maxVal) {
$maxVal = $arr[$i];
$index = $i;
}
}
return $index;
}
$chiSoThap = timChiSoThapNhat($diemArr);
$chiSoCao = timChiSoCaoNhat($diemArr);
echo "Giám khảo tại vị trí $chiSoThap cho điểm thấp nhất: {$diemArr[$chiSoThap]}<br>";
echo "Giám khảo tại vị trí $chiSoCao cho điểm cao nhất: {$diemArr[$chiSoCao]}<br>";
echo str_repeat("*", 30) . "<br>";
// Tính tổng và trung bình (loại bỏ điểm cao và thấp)
$tong = 0;
$soLuong = 0;
for ($i = 0; $i < count($diemArr); $i++) {
echo "Giám khảo #$i: {$diemArr[$i]} điểm<br>";
if ($i != $chiSoThap && $i != $chiSoCao) {
$tong += $diemArr[$i];
$soLuong++;
}
}
$trungBinh = $tong / $soLuong;
echo "<br>Trung bình sau khi loại bỏ: " . number_format($trungBinh, 2) . " điểm";
}
?>
Kết quả với đầu vào 88 90 60 78 100 93:
- Điểm thấp nhất: 60 (giám khảo #2)
- Điểm cao nhất: 100 (giám khảo #4)
- Trung bình 4 điểm còn lại: (88 + 90 + 78 + 93) / 4 = 87.25