PHP版二分検索法

968 ワード

<?php
	//       
	function binary_search($array, $key) {
		binary_search0($array, $key, 0, count($array) - 1);
	}
	//         
	function binary_search0($array, $key, $left_index, $right_index) {
		//        ,         。
		if ($left_index > $right_index) {
			echo "no such element!";
			return;
		}
		
		//         
		$middle_index = round(($left_index + $right_index) / 2);
		
		//             
		if ($key > $array[$middle_index]) { //         
			binary_search0($array, $key, $middle_index + 1, $right_index);
		} else if ($key < $array[$middle_index]) { //         
			binary_search0($array, $key, $left_index, $middle_index - 1);
		} else { //        
			echo "found, the key is $middle_index in the array.";
		}
	}
	
	//      (  :         )
	$array = array(1, 4, 5, 6, 7, 9, 12);

	//     
	binary_search($array, 4); //   :found, the key is 1 in the array.
	binary_search($array, 8); //   :no such element!
?>