<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Вездесущий двоичный поиск...
Псевдокод: Листинг 4.5. Двоичный поиск: новое представление границ диапазона (только если n = 1000 !!!) управление:
  1. i = 512
  2. l = -1
  3. if x[511] < t
  4. l = 1000 - 512
  5.  
  6. while i != 1
  7. /* инвариант: x[l] < t && x[l+i] >=t && i = 2^j */
  8. nexti = i / 2
  9. if x[l + nexti] < t
  10. l = l + nexti
  11. i = nexti
  12. else
  13. i = nexti
  14.  
  15. /* утверждение: i == 1 && x[l] < t && x[l+i] >= t */
  16. p = l+1
  17. if p > 1000 || x[p] != t
  18. p = -1
  19.  

 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2018 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.002949 секунд
Количество запросов к БД: 3, gzip: 2.5kb/6.9kb(64%)