binarySearch that finds exact matching entry. Returns non-zero index when found, or -1 when not found Inspired by sort.Search but makes uses of tri-state comparator to eliminate the last comparison when we want to find exact match, not insertion point.
(n int, compare func(int) (int, error))
| 274 | // Inspired by sort.Search but makes uses of tri-state comparator to eliminate the last comparison when |
| 275 | // we want to find exact match, not insertion point. |
| 276 | func binarySearch(n int, compare func(int) (int, error)) (int, error) { |
| 277 | i, j := 0, n |
| 278 | for i < j { |
| 279 | h := int(uint(i+j) >> 1) // avoid overflow when computing h |
| 280 | c, err := compare(h) |
| 281 | if err != nil { |
| 282 | return -1, err |
| 283 | } |
| 284 | // i ≤ h < j |
| 285 | switch c { |
| 286 | case 0: |
| 287 | // Found exact match |
| 288 | return h, nil |
| 289 | case -1: |
| 290 | j = h |
| 291 | case 1: |
| 292 | i = h + 1 |
| 293 | } |
| 294 | } |
| 295 | |
| 296 | // No match |
| 297 | return -1, nil |
| 298 | } |