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

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