8-1循序搜尋法
循序搜尋法又稱線性搜尋法，是一種最簡單的搜尋法。它的方法是將資料一筆一筆的循序逐次搜尋。所以不管資料順序為何，都是得從頭走訪一次。此法的優點是檔案在搜尋前不需要做任何的處理與排序，缺點是搜尋速度較慢。如果資料沒有重複，找到資料就可終止搜尋的話，在最差的狀況是未找到資料，需做n次比較，最好的狀況則是一次就找到，只需1次比較。
JS sequential.js
var val=0;
var data = new Array();
for (i=0; i<80; i++) {
data[i];
}
for (i=0; i<80; i++) {
data[i]=Math.floor(Math.random()*150)+1;
}
while (val !=-1) {
find=0;
const prompt = require('prompt-sync')();
val = prompt('請輸入搜尋鍵值(1-150)，輸入-1離開：');
for (i=0; i<80; i++) {
if (data[i]==val) {
process.stdout.write('在第'+(i+1) +'個位置找到鍵值'+ data[i]);
find +=1;
}
}
if (find==0 && val !=-1) {
process.stdout.write('#####沒有找到['+val+']#####');
}
console.log();
}
process.stdout.write('資料內容');
console.log();
for (i=0; i<10; i++) {
for (j=0; j<8; j++) {
process.stdout.write((i*8+j+1)+'['+data[i*8+j]+'] ');
}
console.log();
}
PHP sequential.php
if ($_POST['submit']!='送出' ){
echo "
<center>
<form method='post' action='{$_SERVER['[PHP_SELF]']}'>
請輸入欲搜索的數字(1-150)
<input name='number' type='text'>
<input type='submit' name='submit' value='送出''>
</form>
</center>
";
}
else
{
$number=$_POST['number'];
echo "<center>您輸入的數字為：".$number."</center>";
/*
for ($i=0; $i<80; $i++) {
$randval=mt_rand(1,150);
if (in_array($randval, $data)){
$i--;
}else{
$data[]=$randval;
}
}
*/
if (!$_SESSION['data']){
$data = random_num_arr(1, 150, 80);
$_SESSION['data']=$data; //存入
}else{
$data = $_SESSION['data']; //取出
}
$find=0;
for ($i=0; $i<80; $i++) {
if ($data[$i]==$number){
$t=$i+1;
echo "我們在第{$t}筆找到數字{$number}";
$find ++;
unset($_SESSION['data']); //刪除
echo "[<a href=".$_SERVER['PHP_SELF'].">再找一次</a>]";
}
}
if ($find==0) {
echo "抱歉！我們沒有找到數字{$number}<br><br>";
echo "
<center>
<form method='post' action='{$_SERVER['[PHP_SELF]']}'>
請輸入欲搜索的數字(1-150)
<input name='number' type='text'>
<!--
<input name='data' type='hidden' value='{$data}'>
-->
<input type='submit' name='submit' value='送出''>
</form>
</center>
";
}
echo "<br>80個數字陣列為：<br>";
print_arr($data);
}//if
function random_num_arr($a, $b, $num) {
//$a起始數字、$b結束數字、$num取出數字數量
mt_srand((double)microtime()*1000000);
$data =array();
for ($i=0; $i<80; $i++) {
$randval=mt_rand(1,150);
if (in_array($randval, $data)){
$i--;
}else{
$data[]=$randval;
}
}
return $data;
}
function print_arr($arr){
$i=0;
foreach ($arr as $key =>$value){
$key=$key+1;
echo $key."[".$value."]";
echo ($i%8==0 && $i!=0) ? "<br>":" ";
$i++;
}
}
8-2二分搜尋法
如果要搜尋的資料已經事先排序好，則可使用二分搜尋法是將資料分割成兩等份，再比較鍵值與中間值的大小，如果鍵值小於中間值，可確定要找的資料在前半段的元素，否則在後半部。如此分割數次直到找到或確定不存在為止。例如以下已排序數列2、3、5、8、9、11、12、16、18，而所要搜尋值為11時：
JS binary.js
var bin_search=(data, val)=> {
low=0;
high=49;
while (low <=high && val !=-1) {
mid=Math.floor((low+high)/2);
if (val<data[mid]) {
console.log(val,'介於位置',low+1,'[',data[low],'[及中間值',
high+1,'[',data[high],']找左半邊');
high=mid-1;
}
else if (val>data[mid]) {
console.log(val,'介於中間值位置',mid+1,'[',data[mid],'及',
(high+1),']',data[high],']找右半邊');
low=mid+1;
}
else
return mid;
}
return -1;
}
val=1;
var data=new Array();
for (i=0; i<50; i++) {
data[i]=val;
val=val+Math.floor(Math.random()*5)+1;
}
while (true) {
num=0;
const prompt = require('prompt-sync')();
val = prompt('請輸入搜尋鍵值(1-150)，輸入-1離開：');
if (val==-1) break;
num=bin_search(data,val);
if (num==-1) console.log('##### 沒有找到[',val,']#####');
else console.log('在第 ',num+1,'個位置找到[',data[num],']');
}
console.log('資料內容：');
for (i=0; i<5; i++) {
for (j=0; j<10; j++) {
process.stdout.write((i*10+j+1)+'-'+data[i*10+j]+' ');
}
console.log();
}
PHP binary.php
$data=random_num_arr(1,100,50);
$data=sort_select($data);
$_SESSION['data']=$data; //存入
//print_arr($data);
//echo "<br>----------------<br>";
//print_arr(sort_select($data));
$val=1; //起始值
if ($_POST['submit']!='送出' ){
echo "
<center>
<form method='post' action='{$_SERVER['[PHP_SELF]']}'>
請輸入欲搜索的數字(1-150)
<input name='number' type='text'>
<input type='submit' name='submit' value='送出''>
</form>
</center>
";
}
else
{
$number=$_POST['number'];
$val=$number;
echo "您輸入的數字：".$number."<br><br>";
$data = $_SESSION['data']; //取出
$show=0;
while (true) {
//$num=0;
//if ($val==-1) break;
$num=bin_serach($data, $val);
//echo "<br>".$num."<br>";
if ($num==-1){
echo $val."********沒有找到********";
$show=1;
break;
}else{
$num ++;
echo "在{$num}位置找到".$val."OOOOOOOOO找到了OOOOOOOOO";
$show=1;
break;
}
}
if($show==1){
echo "[<a href=".$_SERVER['PHP_SELF'].">再找一次</a>]";
echo "<br>亂數陣列為：<br>";
print_arr($data);
unset($_SESSION['data']); //刪除
}
}
function bin_serach($arr, $val) {
//$data=>搜尋區域 、$val=>搜尋的目標
$low=0;
$high=count($arr)-1;
while ($low <= $high ) {
$mid=intval(($low+$high)/2);
//echo $mid."<br>";
if ($val < $arr[$mid]) {
echo $val."介於位置".$low."[".$arr[$low]."]及中間值"
.$high."[".$arr[$high]."]找左半邊<br>";
$high=$mid-1;
}
elseif ($val > $arr[$mid]) {
echo $val."介於中間值位置".$mid."[".$arr[$mid]."]及"
.$high."[".$arr[$high]."]找右邊<br>";
$low=$mid+1;
}
else
return $mid;
}
return -1;
}
function sort_select ($arr) {
//json_decode($arr);
$count=count($arr);
for ($i=0; $i<$count-1; $i++) {
$smallest=$arr[$i];
$index=$i;
for ($j=$i+1; $j<$count; $j++) {
//由i+1比較起
if($smallest>$arr[$j]){
//找出最小元素
$smallest=$arr[$j];
$index=$j;
}
}
$tmp=$arr[$i];
$arr[$i]=$arr[$index];
//兩個交換
$arr[$index]=$tmp;
}
return $arr;
}
function random_num_arr($a, $b, $num) {
//$a起始數字、$b結束數字、$num取出數字數量
mt_srand((double)microtime()*1000000);
$data =array();
for ($i=0; $i<$num; $i++) {
$randval=mt_rand(1,150);
if (in_array($randval, $data)){
$i--;
}else{
$data[]=$randval;
}
}
return $data;
}
function print_arr($arr){
$i=0;
foreach ($arr as $key =>$value){
$key=$key+1;
echo $key."[".$value."]";
echo ($i%8==0 && $i!=0) ? "<br>":" ";
$i++;
}
}
