<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Вездесущий двоичный поиск...
Исходник: Двоичный поиск, оптимизированная версия: возвращение первого вхождения [C#, code #6, hits: 6388, рейтинг: 3/7,4.91(2754)] +
автор: this [добавлен: 10.03.2002] управление:
  1. class BSearch
  2. {
  3. static public int Go(int[] x, int n, int t)
  4. {
  5. int l = -1, u = n, p = 0, m = 0;
  6.  
  7. while (l + 1 != u) {
  8. m = (l + u) /2;
  9.  
  10. if (x[m] < t) {
  11. l = m;
  12. } else {
  13. u = m;
  14. }
  15. }
  16.  
  17. p = u;
  18. if (p >= n || x[p] != t) {
  19. p = -1;
  20. }
  21. return p;
  22. }
  23. }
Реализация основной версии двоичного поиска.
В отсортированном массиве ищет элемент за не более чем log2n проходов, где n - длинна массива.
Если искомых элементов в массиве несколько - возвращается первый из них.

+добавить реализацию
 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2021 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.006891 секунд
Количество запросов к БД: 9, gzip: 3.0kb/8.6kb(66%)