Задача: Бинарный поиск в массиве и его разновидности
Исходник: Неоптимизированная версия: возвращение произвольного вхождения, язык: php [code #9, hits: 6269]
автор: this [добавлен: 10.05.2002]
  1. function BaseBSearch($x, $t) {
  2. if (!is_array($x)) return -1;
  3. $n = sizeof($x);
  4. $l = 0;
  5. $u = $n - 1;
  6. $p = 0;
  7. $m = 0;
  8.  
  9. while (true) {
  10. if ($l > $u) {
  11. $p = -1;
  12. break;
  13. }
  14.  
  15. $m = ceil(($l + $u) / 2);
  16.  
  17. if ($x[$m] < $t) {
  18. $l = $m + 1;
  19. } else if ($x[$m] == $t) {
  20. $p = $m;
  21. break;
  22. } else if ($x[$m] > $t) {
  23. $u = $m - 1;
  24. }
  25. }
  26.  
  27. return $p;
  28. }
Реализация базовой, неоптимизированной версии двоичного поиска.
В отсортированном массиве ищет элемент за не более чем log2n проходов, где n - длинна массива.
Если искомых элементов в массиве несколько - возвращается произвольный из них.
Тестировалось на: Apache 1.3.33, PHP 5.0

+добавить реализацию