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

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