Find it fast.
Or wait forever.

// Exponential search: find the range first, then binary search.
// Useful when the array is huge, or its end is expensive to reach.
fn exponential_search(arr: &[i32], target: i32) -> Option<usize> {
    if arr.is_empty() { return None; }
    if arr[0] == target { return Some(0); }

    // Double the bound until arr[bound] >= target or we run off the end.
    let mut bound = 1usize;
    while bound < arr.len() && arr[bound] < target {
        bound *= 2;
    }

    // Binary search the bracketed window [bound/2, bound].
    let lo = bound / 2;
    let hi = bound.min(arr.len() - 1) + 1;
    arr[lo..hi].binary_search(&target).map(|i| lo + i).ok()
    // O(log i) where i is the target's index.
    // Faster than plain binary search when the target is near the front.
}

// partition_point is Rust's lower_bound / upper_bound.
fn equal_range(arr: &[i32], target: i32) -> std::ops::Range<usize> {
    let lo = arr.partition_point(|&x| x <  target);
    let hi = arr.partition_point(|&x| x <= target);
    lo..hi
    // Every index where arr[i] == target, in O(log n).
    // Empty range if the target is absent. This is C++'s equal_range.
}

fn main() {
    let data = vec![1, 2, 3, 3, 3, 5, 7, 9];
    println!("{:?}", equal_range(&data, 3));         // 2..5
    println!("{:?}", equal_range(&data, 4));         // 5..5 (empty)
    println!("{:?}", exponential_search(&data, 7));  // Some(6)
}

#include <stddef.h>

/* Plain binary search returning a pointer, or NULL. */
static int *bsearch_int(int target, const int *arr, size_t n) {
    int lo = 0, hi = (int)n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if      (arr[mid] == target) return (int *)&arr[mid];
        else if (arr[mid]  < target) lo = mid + 1;
        else                          hi = mid - 1;
    }
    return NULL;
}

/* Exponential search: bracket the range, then binary search it. */
int *exponential_search(const int *arr, size_t n, int target) {
    if (n == 0)           return NULL;
    if (arr[0] == target) return (int *)arr;

    size_t bound = 1;
    while (bound < n && arr[bound] < target)
        bound *= 2;

    size_t lo = bound / 2;
    size_t hi = bound < n ? bound : n - 1;
    return bsearch_int(target, arr + lo, hi - lo + 1);
}

/* Lower bound: first index where arr[i] >= target. */
size_t lower_bound(const int *arr, size_t n, int target) {
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else                    hi = mid;
    }
    return lo;
}

/* Upper bound: first index where arr[i] > target. */
size_t upper_bound(const int *arr, size_t n, int target) {
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target) lo = mid + 1;
        else                     hi = mid;
    }
    return lo;
}
/* [lower_bound, upper_bound) brackets every occurrence of target. */
/* That half-open range is exactly C++'s equal_range.              */

use std::collections::HashMap;

// The real Bitcoin Core split: a hash map for point lookups,
// a sorted structure for range scans. Simplified with a Vec here;
// Core uses LevelDB, which keeps keys sorted on disk.
struct UtxoSet {
    // O(1) point lookup: does this exact coin exist?
    by_outpoint: HashMap<([u8; 32], u32), u64>,

    // O(log n) range scan, sorted by scriptpubkey.
    // (scriptpubkey, txid, vout, satoshis)
    by_script: Vec<([u8; 25], [u8; 32], u32, u64)>,
}

impl UtxoSet {
    // O(1): spend-time check. Is this coin still unspent?
    fn contains(&self, txid: &[u8; 32], vout: u32) -> bool {
        self.by_outpoint.contains_key(&(*txid, vout))
    }

    // O(log n + k): which coins does this address own?
    fn utxos_for_script(
        &self,
        script: &[u8; 25],
    ) -> &[([u8; 25], [u8; 32], u32, u64)] {
        let lo = self.by_script.partition_point(|(s, ..)| s <  script);
        let hi = self.by_script.partition_point(|(s, ..)| s <= script);
        &self.by_script[lo..hi]
        // partition_point is binary search: O(log n) to find lo and hi,
        // then O(k) to hand back the slice. A hash map cannot do this.
    }
}

#include <stdint.h>
#include <stddef.h>
#include <string.h>

/* A UTXO entry, sorted by scriptpubkey so a node can find
 * every coin owned by an address with one binary search. */
typedef struct {
    uint8_t  scriptpubkey[25];
    uint8_t  txid[32];
    uint32_t vout;
    uint64_t amount_satoshis;
} Utxo;

/* Find the FIRST utxo with this scriptpubkey. O(log n).
 * Keep the result low: on a match, search left for an
 * earlier one. The caller then scans forward for the rest. */
const Utxo *find_first_utxo(const Utxo *utxos,
                            size_t n,
                            const uint8_t script[25]) {
    int lo = 0, hi = (int)n - 1, result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int c = memcmp(utxos[mid].scriptpubkey, script, 25);
        if      (c == 0) { result = mid; hi = mid - 1; }
        else if (c <  0) lo = mid + 1;
        else             hi = mid - 1;
    }
    return result >= 0 ? &utxos[result] : NULL;
}
/* O(log n) to find the first match, then a linear scan
 * forward over the k coins that share the scriptpubkey.
 * O(log n + k), the same shape as Rust's partition_point. */