nx_binary_search.nx source

1// nx_binary_search.nx -- canonical binary search on a sorted nx_int array. 2// 3// Returns the index of `key` if present, else -1. Uses the 4// overflow-safe midpoint `lo + (hi - lo) / 2` per Bottenbruch 1962. 5// 6// genealogy_id: bottenbruch_1962_correct_binary_search 7// lineage_id: sorted_key_lookup 8// references: Mauchly 1946 (Moore School lectures); Bottenbruch CACM 1962; 9// Knuth TAoCP Vol 3 6.2.1. 10// license: public_domain (pre-1995 classical result) 11// 12// Tier-aware: arr elements + key are nx_int (swappable via nx_tier.nx); 13// indices are nx_idx. No bare i64 anywhere in the API surface. 14 15// nx_safety_envelope: 16// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 17// sil_target: SIL1 18// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail] 19// verdict: NOT_YET_EVALUATED 20 21import "nx_syscalls.nx" 22import "nx_tier.nx" 23 24// Search sorted `arr` of length `n` for `key`. Returns index or -1. 25func nx_binary_search(arr: *nx_int, n: nx_idx, key: nx_int) -> nx_idx { 26 var lo: nx_idx = 0 27 var hi: nx_idx = n 28 while lo < hi { 29 let mid: nx_idx = lo + (hi - lo) / 2 30 if arr[mid] == key { return mid } 31 if arr[mid] < key { lo = mid + 1 } 32 if arr[mid] > key { hi = mid } 33 } 34 return -1 35} 36 37// Lower-bound variant: first index i where arr[i] >= key, or n if all 38// elements < key. Useful for range queries / insertion points. 39func nx_binary_search_lower_bound(arr: *nx_int, n: nx_idx, key: nx_int) -> nx_idx { 40 var lo: nx_idx = 0 41 var hi: nx_idx = n 42 while lo < hi { 43 let mid: nx_idx = lo + (hi - lo) / 2 44 if arr[mid] < key { lo = mid + 1 } 45 if arr[mid] >= key { hi = mid } 46 } 47 return lo 48}