Задача: Бинарный поиск в массиве и его разновидности
Псевдокод: Листинг 4.7. Двоичный поиск при n = 1000, финальная версия
  1. i = 512
  2. l = -1
  3. if (x[511] < t) l = 1000 - 512
  4. /* утверждение: x[l] < t && x[l + 512] >= t */
  5. if (x[l+256] < t) l += 256
  6. /* утверждение: x[l] < t && x[l + 256] >= t */
  7. if (x[l+128] < t) l += 128
  8. /*...*/
  9. if (x[l+64] < t) l += 64
  10. /*...*/
  11. if (x[l+32] < t) l += 32
  12. /*...*/
  13. if (x[l+16] < t) l += 16
  14. /*...*/
  15. if (x[l+8] < t) l += 8
  16. /*...*/
  17. if (x[l+4] < t) l += 4
  18. /*...*/
  19. if (x[l+2] < t) l += 2
  20. /* утверждение: x[l] < t && x[l + 2] >= t */
  21. if (x[l+1] < t) l += 1
  22. /* утверждение: x[l] < t && x[l + 1] >= t */
  23.  
  24. p = l + 1
  25. if p > 1000 || x[p] != t
  26. p = -1
  27.