Помогни ни да направим Uroci.net по - богат! Добави урок

Binary search algorithm

PHP » PHP
Strike   трудност:    видян: 5433

Няма да ви се наложи да го използвате но поне ще се запознаете с него

повече инфо: 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";
}

 

 



Коментари (2)

dzv3r0 на 03.01 2010 в 10:20ч.
Ами, в такъв случай, благодаря ти че си отделил ог времето си за да загубиш това на останалите (ако приемем че никой няма да използва подобен алгоритъм).

Като за начало би било добре да сортираш масива (в този урок той е сортиран но това в риалния живот се случва мнооого радко), направил си променлива с размера на масива, но после вместо да я ползваш ти караш машината отново да провери размера че даже и да извади единица
по-рационално е този ред:
$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 какво е и какво дири тука.

Иначе, радвам се че си обърнал внимание на една интересна и важна тема в програмирането.

Поздрави
UnAfraid на 26.07 2010 в 16:48ч.
Имал е предвит \n нов ред аз небих го ползвал по този начин, но PHP_EOL е далеч по правилен. :)

Регистрирайте се, за да добавите коментар


Калдейта ЕООД - © 2003-2010. Всички права запазени.
Препоръчваме: IT Новини