Notebooks · lib/algo/legacy/searches

lib/algo/legacy/searches.viv

Look inside this program

Atlas
The program’s map: every function and which calls which.
There’s no recorded run of this program yet.

Shift+Enter in a cell runs it and moves to the next. Running a cell runs every cell above it too, as one program.

[1]lines 1–39

# Generated by tools/algo/legacy.py from the corpus: do not edit.
# Two hand-written binary searches: lib/nprandom's searchsorted(side='right') and the fasta benchmark's bisect.bisect.
# Element comparisons are routed through lib/algo/legacy/order.viv; nothing else changes.
from algo.legacy.order import lg_le, lg_lt

# from lib/nprandom/legacy.viv: npr_lg_search

#| searchsorted(u, side='right') in a non-decreasing cdf: how many entries are <= u.
def npr_lg_search(cdf: Arr, u) {
    lo = 0
    hi = len(cdf)
    while lo < hi {
        mid = floor((lo + hi) / 2)
        if lg_le(cdf[mid], u) {
            lo = mid + 1
        }
        else {
            hi = mid
        }
    }
    return lo
}

# from study/benchmarks/viv/bg/fasta.viv: bisect

def bisect(a: Arr, x) {
    lo = 0
    hi = len(a)
    while lo < hi {
        mid = (lo + hi) // 2
        if lg_lt(x, a[mid]) {
            hi = mid
        }
        else {
            lo = mid + 1
        }
    }
    return lo
}