<?php
if ($N && $target && $MAX) {
for ($i=0;$i<$N;$i++) {
$number[$i] = rand(1,$MAX);
}
$now= time();
QuickSort (0,$N-1);
$delay = time()-$now;
echo "정렬에 ".$delay."초 걸림<br>";
for($i=0;$i<$N;$i++)
echo "<div style='width:80px;float:left;'>".$i.":".$number[$i]."</div>";
echo "<div style='clear:both'></div>".$target."이/가 존재하는지 ".$s."로 알아보면<br>";
if ($s=='순차검색') echo SequentialSearch ($number,$target,$N);
else echo BinarySearch ($number,$target,0,$N-1,0);
}
?>
<form method action=BinSearch.php>
최대값은?
<input type=text name=MAX>
수열의 크기는?
<input type=text name=N>
검색할 숫자는?
<input type=text name=target>
검색방법은?
<select name=s>
<option>순차검색</option>
<option>이진검색</option>
</select>
<input type=submit value='Go'>
</form>
<?
// 순차 검색 함수 (Sequential Search)
function SequentialSearch ($list, $target, $N) {
for($i=0;$i<$N;$i++){
if ($list[$i]==$target) return $i."번째에 성공";
}
return $i."번째에 실패";
}
// 이진 검색 함수 (Binary Search)
function BinarySearch ($list, $target, $p, $q, $cnt) {
$cnt++;
if ($p<=$q) {
$i = (int)(($p+$q)/2);
echo "위치 ".$i." ";
if ($list[$i]==$target) {echo "들을 훑은 후 ".$cnt."번만에 성공"; return;}
else if ($target<$list[$i]) BinarySearch ($list, $target, $p, $i-1,$cnt);
else BinarySearch($list, $target, $i+1, $q, $cnt);
}
else {echo "들을 훑은 후 ".$cnt."번만에 실패"; return;}
}
function QuickSort ($p,$q) {
global $number;
if ($p<$q) {
$i=$p; $j=$q;
$c = (int)(($i+$j)/2);
// echo $c." ".$number[$c]." ";
while ($i<$j) {
if ($number[$i]>$number[$c]) {
while ($number[$j]>$number[$c]){
$j--;
}
if ($j==$c) $c=$i;
$temp = $number[$i];
$number[$i]=$number[$j];
$number[$j]=$temp;
}
if ($i<$c) $i++;
if ($number[$j]<$number[$c]) {
while ($number[$i]<$number[$c]){
$i++;
}
if ($i==$c) $c=$j;
$temp = $number[$i];
$number[$i]=$number[$j];
$number[$j]=$temp;
}
if ($c<$j) $j--;
}
QuickSort($p,$c);
QuickSort($c+1,$q);
}
else return;
}
?>