Binary search code

[tthlan]

Binary search with array in sort increase
Try mysearch() or myfind() function, the advance function is fastsearch()

Code: Select all

<?php
function mysearch(int $dataValue, $list){
    $lowerBound = 0;
    $upperBound = sizeof($list);
	$comparisons = 1;

    while ($lowerBound < $upperBound) {
		$comparisons++;
        $midIndex = $lowerBound + ($upperBound - $lowerBound) / 2;
		//printf($lowerBound . " - " . $upperBound . " - " . $midIndex . "<br>");
        if ($list[$midIndex] == $dataValue) {
			printf("<br>Tong so phep so sanh da thuc hien: %d", --$comparisons);
            return $midIndex;
        } else if ($list[$midIndex] < $dataValue) {
            $lowerBound = $midIndex + 1;
			//printf("<br>lowerBound" . $lowerBound);
        } else {
            $upperBound = $midIndex - 1;
			//printf("<br>upperBound" . $upperBound);
        }
    }
	printf("<br>Tong so phep so sanh da thuc hien: %d", --$comparisons);
    return -1;
}

Code: Select all

function myfind(int $data, $list) {
	$lo = 0;
	$hi = sizeof($list) - 1;
	$mid = -1;

	$comparisons = 1;      
	$index = -1;
 
	while($lo <= $hi) {
		//printf("<br>So sanh lan thu %d  \n" , $comparisons ) ;
		//printf("<br>lo : %d, list[%d] = %d\n", $lo, $lo, $list[$lo]);
		//printf("<br>hi : %d, list[%d] = %d\n", $hi, $hi, $list[$hi]);
		$mid =( ($hi+$lo )/ 2);
		$comparisons++;
 
		//// phan tu chot (probe) tai vi tri trung vi
		//printf("<br>Vi tri trung vi = %d\n",$mid);

		//exit();
		// tim thay du lieu
		if($list[$mid] == $data) {
			$index = $mid;
			break;
		}else {
			//printf("<br>====>%d  --- %d\n", $list[$mid] , $data);
			//printf("<br>lo - hi ====>%d  --- %d\n", $lo , $hi);
			if($list[$mid] < $data) {
				// neu du lieu co gia tri lon hon, tim du lieu trong phan lon hon 
				$lo = $mid + 1;
			}else {
				// neu du lieu co gia tri nho hon, tim du lieu trong phan nho hon 
				$hi = $mid - 1; 
			}
		}
	}
	printf($index);
	printf("<br>Tong so phep so sanh da thuc hien: %d", --$comparisons);
	return $index;
} 

Code: Select all

function fastsearch(int $data, $list) {
   $lo = 0;
   $hi = sizeof($list) - 1;
   $mid = -1;
            
   $comparisons = 1;      
 
	while($lo <= $hi) {
		//printf("<br>So sanh lan thu %d  \n" , $comparisons ) ;
		//printf("<br>lo : %d, list[%d] = %d\n", $lo, $lo, $list[$lo]);
		//printf("<br>hi : %d, list[%d] = %d\n", $hi, $hi, $list[$hi]);

		$comparisons++;

		//printf($hi);

		// phan tu chot (probe) tai vi tri trung vi
		$mid = $lo + (($hi - $lo) / ($list[$hi] - $list[$lo])) * ($data - $list[$lo]);
		//printf("<br>Vi tri trung vi = %d\n",$mid);

		//exit();
		// tim thay du lieu
		if($list[$mid] == $data) {
			//$index = $mid;
			printf("<br>Tong so phep so sanh da thuc hien: %d", $comparisons);
			return $mid;
			break;
		}else {
			//printf("<br>====>%d  --- %d\n", $list[$mid] , $data);
			//printf("<br>lo - hi ====>%d  --- %d\n", $lo , $hi);
			if($list[$mid] < $data) {
			// neu du lieu co gia tri lon hon, tim du lieu trong phan lon hon 
									$lo = $mid + 1; 
			}else {
			// neu du lieu co gia tri nho hon, tim du lieu trong phan nho hon 
									$hi = $mid - 1;
			}
		}
   }
	//printf($index);
	printf("<br>Tong so phep so sanh da thuc hien: %d", --$comparisons);
	return -1;
}

Code: Select all

	$list = [10, 14, 19, 26, 27, 31, 33, 35];
	//Tim vi tri cua phan tu 33
	
	printf("<br>=======myfind=======");
	$time_start = microtime(true);
	printf("<br>$time_start");
	$location = myfind(22, $list);
	
	$time_end = microtime(true);
	$time = number_format($time_end - $time_start, 8);
	printf("<br>$time");
	
	printf("<br>=======fastsearch=======");
	$time_start = microtime(true);
	
	$location = fastsearch(22, $list);
	
	$time_end = microtime(true);
	$time = number_format($time_end - $time_start, 8);
	printf("<br>" . $time);
	
	printf("<br>=======mysearch=======");
	$time_start = microtime(true);
	
	$location = mysearch(22, $list);
	
	$time_end = microtime(true);
	$time = number_format($time_end - $time_start, 8);
	printf("<br>$time");
 
	// Neu tim thay phan tu 
	if($location != -1)
		printf("<br>Tim thay phan tu tai vi tri: %d" ,($location+1));
	else
		printf("<br>Khong tim thay phan tu.");