Няма да ви се наложи да го използвате но поне ще се запознаете с него
повече инфо: http://en.wikipedia.org/wiki/Binary_search_algorithm
Примера ще бъде на php някой ако държи ще го напиша и на c++
$A=array(1,3,5,8,13,24,33,46,50,51,90,980,2000);
$size=count($A);
$val=0;
function binarySearch($value,$starting,$ending)
{
if($ending<$starting)
{
return -1;
}
$mid=intVal(($starting+$ending)/2);
global $A;
$_I1=$A[$mid];
if($_I1===$value)
{
return $mid;
}
else
{
if($_I1>$value)
{
$ending=$mid-1;
}
else
{
if($_I1<$value)
{
$starting=$mid+1;
}
}}
return binarySearch($value,$starting,$ending);
}
print_r($A);
echo "Give a value to search:";
$fp=fopen("php://stdin","r");
$val=rtrim(fgets($fp,65536));
fclose($fp);
$y=binarySearch(intval($val),0,count($A)-1);
if($y>=0)
{
echo $val, " ", "is at position", " ", $y, "n";
}
else
{
echo $val, " ", "not found in the array...", "n";
}
Като за начало би било добре да сортираш масива (в този урок той е сортиран но това в риалния живот се случва мнооого радко), направил си променлива с размера на масива, но после вместо да я ползваш ти караш машината отново да провери размера че даже и да извади единица
по-рационално е този ред:
$y=binarySearch(intval($val),0,count($A)-1);
да изглежда така:
$y=binarySearch(intval($val),0,$size-1);
както и:
echo $val, " ", "is at position", " ", $y, "n";
да бъде:
echo $val . " is at position " . $y . "n";
аналогично и за следващия, но се чудя това n какво е и какво дири тука.
Иначе, радвам се че си обърнал внимание на една интересна и важна тема в програмирането.
Поздрави