圖說演算法使用JavaScript(十九)

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();
}