Minimize missing of messages when there's gaps in the ids in scaleout
- When binary search fails, return the last valid search range
  so that we can pick the smallest value bigger than the target id.
- Added unit tests for new behavior.

#1831
samples
update on samples after code review