Программирование в целом - Алгоритмы двоичного поиска

Question

Учитывая массив $ массив из N чисел и ключ $ key, напишите алгоритм двоичного поиска на простом английском языке.Если $ array содержит $ key, вернуть индекс ключа $;в противном случае верните -1. ​​

Может кто-нибудь показать мне, как это сделать?

Answer 1

Не похоже, что я должен дать вам код здесь, но, может быть, это описание может помочь?

1. Сортировать список.

2. Let i = length / 2

3. Сравните термин по индексу i с вашим ключом.

   a.Если они равны, вернуть индекс.

   b.Если ключ больше этого термина, повторите 3 (recurse) в верхней половине списка i = (i + length) / 2 (или (i + top) / 2 в зависимости от того, как вы реализуете)

   c.Если ключ меньше этого термина, повторите 3 в нижней половине i = i/2 или (i + bottom)/2

Остановите рекурсию, если / когда новый i совпадает со старым i.Это означает, что вы исчерпали поиск.Возвращаемое значение -1

---

Будьте осторожны с ошибками, которые могут привести к исключению некоторых терминов по ошибке или к бесконечной рекурсии, но это общая идея.Довольно просто.

Думайте об этом, как о игре «Угадай число» для чисел от 1 до 100. Вы делаете предположение, я говорю вам выше или ниже.Вы говорите 50, я говорю ниже.Вы говорите 25, я говорю выше.Вы говорите 37 ...

Answer 2

Я знаю, что уже немного поздно :), но все равно примите это. Это также показывает, что рекурсивная функция работает быстрее, чем in_array ()

 function binarySearch($A,$value,$starting,$ending)
    {
       if($ending<$starting)
       {
          return -1;
       }
       $mid=intVal(($starting+$ending)/2);

       if($value===$A[$mid])
          {
              return $mid;
          }
       else if($value<$A[$mid])
          {
             $ending=$mid-1;
          }
       else if($value>$A[$mid])
          {
             $starting=$mid+1;
          }

       return binarySearch($A,$value,$starting,$ending);
    }

    for($i;$i<1000000;$i++){
       $arr[$i]=$i;
    }
    $value =99999;

    $msc=microtime(true);
    $pos = in_array($value,$arr);
    $msc=microtime(true)-$msc; 

    echo "Time taken for in_array() : ".round($msc*1000,3).' ms <br>';
    if($pos>0)
    echo $value .' found.';
    else
    echo $value .' not found';

    echo "<br><br>";
    $msc=microtime(true);
    $pos = binarySearch($arr,$value ,0,1000000);
    $msc=microtime(true)-$msc; 

    echo "Time taken for recursive function : ".round($msc*1000,3).' ms<br>';
    if($pos>=0)
    echo $value .' found.';
    else
    echo $value .' not found';

Ouput:

Time taken for in_array() : 5.165 ms 
99999 found.

Time taken for recursive function : 0.121 ms
99999 found.

Answer 3

Вот лучшее нерекурсивное решение.

function fast_in_array($elem, $array){
   $top = sizeof($array) -1;
   $bot = 0;

   while($top >= $bot)
   {
      $p = floor(($top + $bot) / 2);
      if ($array[$p] < $elem) $bot = $p + 1;
      elseif ($array[$p] > $elem) $top = $p - 1;
      else return TRUE;
   }

   return FALSE;
}