Searching

BINS — Binary Search

solvedbrowser + CLI Problem statement Open in the workbench Download .bl

# Rosalind: BINS — Binary Search
# https://rosalind.info/problems/bins/
#
# Given: Two positive integers n and m, a sorted array A[1..n], and m keys.
# Return: For each key, an index j with A[j] = key, or -1 if there is none.

let a = [10, 20, 30, 40, 50]
let queries = [40, 10, 35, 15, 40, 20]

# Halve the live window until it is empty. Rosalind indexes from 1, so the
# answer is the zero-based position plus one.
fn binary_search(sorted, key) {
    let lo = 0
    let hi = len(sorted) - 1
    let found = -1
    while lo <= hi and found == -1 {
        let mid = int((lo + hi) / 2)
        let value = sorted[mid]
        if value == key then {
            found = mid + 1
        } else {
            if value < key then lo = mid + 1 else hi = mid - 1
        }
    }
    found
}

let result = queries |> map(|k| str(binary_search(a, k))) |> join(" ")

println("Result:   " + result)
println("Expected: 4 1 -1 -1 4 2")

fn test_bins_locates_every_key() {
    assert result == "4 1 -1 -1 4 2", "BINS: got " + result
}

MED — Median

solvedbrowser + CLI Problem statement Open in the workbench Download .bl

Quickselect: recurses into one side only, so it answers the question without sorting. Cross-checked against sorting in the assertion.

# Rosalind: MED — Median
# https://rosalind.info/problems/med/
#
# Given: A positive integer n, an array A[1..n] of integers, and a number k.
# Return: The k-th smallest element of A.

let a = [2, 36, 5, 21, 8, 13, 11, 20, 5, 4, 1]
let k = 8

# Quickselect: partition around a pivot, then recurse into the side that holds
# the k-th element instead of both. Sorting would answer the question too and do
# more work than asked — this is the problem's point. The array holds 5 twice,
# so the equal region is kept separate rather than folded into one side.
fn select_kth(xs, rank) {
    if len(xs) <= 1 {
        xs[0]
    } else {
        let pivot = xs[int(len(xs) / 2)]
        let below = xs |> filter(|v| v < pivot)
        let equal = xs |> filter(|v| v == pivot)
        let above = xs |> filter(|v| v > pivot)

        if rank <= len(below) {
            select_kth(below, rank)
        } else {
            if rank <= len(below) + len(equal) {
                pivot
            } else {
                select_kth(above, rank - len(below) - len(equal))
            }
        }
    }
}

let result = select_kth(a, k)

println("Result:   " + str(result))
println("Expected: 13")
println("Sorted:   " + str(sort(a)))

fn test_med_kth_smallest() {
    assert result == 13, "MED: got " + str(result)
    assert result == sort(a)[k - 1], "MED: disagrees with sorting, got " + str(result)
}