binary search

Binary search

x'y

Binary search performs a binary search for y in a list x, assuming x is sorted in ascending order. It returns the smallest index i such that y would sort after (or matches) x[i], or -1 if no such index exists.

binary search is right atomic.

  0 2 4 6 8 10'5
 2
   0 2 4 6 8 10'-10 0 4 5 6 20
 -1 0 2 2 3 5