algorytm.org

Implementacja w Php

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Szukanie połówkowe (binarne) - Implementacja w Php
Ocena użytkownikóww: *****  / 2
SłabyŚwietny
Nadesłany przez Karol Nowacki, 14 kwietnia 2011 13:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

szukanie_polowkowe_1_php.php:
<?php

/**
 *
 * Funkcja przeszukuje binarnie tablicę $array w poszukiwaniu wartości $value
 * W przypadku powodzenia zwracany jest index tablicy. W przecienym razie wartość false
 *
 * www.algorytm.org
 *
 * @param array[int]mixed $array posortowana tablica
 * @param mixed $value szukana wartość
 * @param boolean $strict jezeli jest true porównywane jest również typ zmiennej
 * @return integer|false
 */
function binsearch(&$array, $value, $strict = false) {

	if (!is_array($array))
		return false;

	$l = 0;
	$p = count($array)-1;

	while ($l <= $p) {

		$s = floor(($l+$p)/2);

		if (($strict && $array[$s] === $value) || (!$strict && $array[$s] == $value))
			return $s;

		if ($array[$s] > $value)
			$p = $s-1;
		if ($array[$s] < $value)
			$l = $s+1;

	}

	return false;

}

// Inicjacja testowek tablicy losowymi wartościami
$a = array();
for ($i=0; $i<100; $i++)
	$a[$i] = rand(0, 1000);

// Szukana wartość
$v = $a[0];

// sortujemy tablicę
sort($a);

//szukamy
if (($index = binsearch($a, $v)) !== false)
	echo "Znaleziono wartość $v w tablicy \$a pod indeksem $index".PHP_EOL;
else
	echo "Szukana wartość $v nie została znaleziona".PHP_EOL;








Dodaj komentarz