fork download
  1. def query_sum(seq, target):
  2. def bsearch(l, r):
  3. while r >= l:
  4. mid = l + (r - l) // 2
  5. s = sum(seq[mid:mid + 2])
  6. if s == target:
  7. return mid
  8. elif s > target:
  9. r = mid - 1
  10. else:
  11. l = mid + 1
  12. return -1
  13. i = bsearch(0, len(seq) - 1)
  14. if i < 0:
  15. return False
  16. print("Yes sum exist with pair {} {}".format(*seq[i:i + 2]))
  17. return True
  18.  
  19. x = [1, 2, 3, 4, 5]
  20. y = [1, 2, 4, 8, 16]
  21.  
  22. query_sum(x, 7)
  23. query_sum(y, 3)
Success #stdin #stdout 0.02s 9040KB
stdin
Standard input is empty
stdout
Yes sum exist with pair 3 4
Yes sum exist with pair 1 2