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))
| 283 | // Inspired by sort.Search but makes uses of tri-state comparator to eliminate the last comparison when |
| 284 | // we want to find exact match, not insertion point. |
| 285 | func binarySearch(n int, compare func(int) (int, error)) (int, error) { |
| 286 | i, j := 0, n |
| 287 | for i < j { |
| 288 | h := int(uint(i+j) >> 1) // avoid overflow when computing h |
| 289 | c, err := compare(h) |
| 290 | if err != nil { |
| 291 | return -1, err |
| 292 | } |
| 293 | // i ≤ h < j |
| 294 | switch c { |
| 295 | case 0: |
| 296 | // Found exact match |
| 297 | return h, nil |
| 298 | case -1: |
| 299 | j = h |
| 300 | case 1: |
| 301 | i = h + 1 |
| 302 | } |
| 303 | } |
| 304 | |
| 305 | // No match |
| 306 | return -1, nil |
| 307 | } |