Bake_WP空間

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++;
	}

}