Every language
12 languages, copy-ready. One at a time with syntax highlighting, or all inline.
JSJavaScript
// lower_bound: smallest i where arr[i] >= target — index AND insertion point:
function lowerBound(arr, target) {
let lo = 0, hi = arr.length; // half-open [lo, hi) — hi is N, not N-1
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1); // overflow-safe midpoint idiom
if (arr[mid] < target) lo = mid + 1;
else hi = mid; // mid stays a candidate
}
return lo; // the index, or where target inserts
}
const a = [1, 3, 3, 5, 7];
lowerBound(a, 3); // 1 — leftmost 3
lowerBound(a, 4); // 2 — absent: the slot 4 would takeNo stdlib binary search — hand-roll the half-open loop. JS numbers are doubles, so (lo + hi) / 2 cannot overflow the way it does in C or Java; >> 1 still earns its keep by keeping mid an integer for free, and the line ports unchanged to every language where the overflow is real.
TSTypeScript
// found ⇒ index; absent ⇒ -(insertionPoint) - 1 — the Java encoding:
function binarySearch(arr: readonly number[], target: number): number {
let lo = 0, hi = arr.length - 1; // closed [lo, hi]
while (lo <= hi) { // <= — a one-element window still runs
const mid = (lo + hi) >>> 1;
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return ~lo; // == -(lo) - 1, the complement trick
}
const idx = binarySearch([1, 3, 5], 4); // -3
const ins = ~idx; // 2 — decode the insertion pointThe ~ complement trick from Java tradition: ~x === -(x + 1), so ~lo encodes the insertion point and ~idx decodes it. The mixed return (index OR negative) forces a >= 0 check on every caller — the price of one function answering two different questions.
GoGo
import "sort"
nums := []int{1, 3, 3, 5, 7}
i := sort.SearchInts(nums, 4) // 2 — smallest i with nums[i] >= 4
found := i < len(nums) && nums[i] == 4 // false — the check you must not skip
// the general form — smallest i in [0, n) where f(i) is true:
j := sort.Search(len(nums), func(k int) bool { return nums[k] >= 3 })sort.Search answers a PREDICATE, not a lookup: the smallest i where f(i) is true — and it returns n when none is, which is exactly the insertion point. 'Found' is always your own bounds check; forgetting the i < len(nums) guard panics on every absent probe.
RsRust
let arr = [1, 3, 3, 5, 7];
// Result: which boundary you got is IN the type:
let hit = arr.binary_search(&3); // Ok(1) — index of SOME 3
let miss = arr.binary_search(&4); // Err(2) — absent; Err IS the insertion point
// leftmost of the equals — binary_search does NOT promise leftmost:
let left = arr.partition_point(|x| x < 3); // 1 — the predicate-only siblingbinary_search returns Result<usize, usize> — Ok is an index of a match (unspecified which when equals exist); Err IS the insertion point, no arithmetic to decode. partition_point(|x| x < t) is the predicate-only sibling that gives the leftmost boundary directly — Rust's lower_bound.
PHPPHP
function lowerBound(array $a, $target): int
{
$lo = 0;
$hi = count($a); // half-open [lo, hi)
while ($lo < $hi) {
$mid = intdiv($lo + $hi, 2); // integer midpoint — never a float
if ($a[$mid] < $target) $lo = $mid + 1;
else $hi = $mid;
}
return $lo; // the index, or the insertion point
}No stdlib binary search in PHP. intdiv($lo + $hi, 2), NOT ($lo + $hi) / 2 — the division operator returns a float, and at huge indexes float rounding silently drifts the midpoint. 64-bit PHP makes the lo + hi sum itself overflow-safe; intdiv keeps the whole computation in integers.
PyPython
import bisect
a = [1, 3, 3, 5, 7]
i = bisect.bisect_left(a, 3) # 1 — first slot that could hold a 3
j = bisect.bisect_right(a, 3) # 3 — first slot AFTER the 3s
found = i != j # present iff the two boundaries differ
count = j - i # 2 — length of the equals-run, no scan
bisect.insort(a, 4) # stay sorted: bisect + insert, O(n) shiftbisect_left vs bisect_right is the WHOLE difference when equals exist — left lands on the first equal, right just past the last, and j - i is the run length. Neither flags absence: both always return an insertion point, so 'found' is your own comparison (a[i] == target).
C#C#
int[] a = { 1, 3, 3, 5, 7 };
int hit = Array.BinarySearch(a, 3); // 1 — SOME index within the 3s
int miss = Array.BinarySearch(a, 4); // -3 — the complement of insertion 2
int ins = ~miss; // 2 — ~x == -(x + 1) is the decode
if (hit < 0) { /* absent; ~hit is the insertion point */ }A miss returns the bitwise COMPLEMENT of the insertion point — decode with ~result, arithmetically identical to Java's -(r) - 1. .NET 8's SearchValues<T> is .NET's newer baked-in search, but it is vectorized membership scanning (IndexOfAny over spans), not sorted-array binary search — a different tool for unsorted haystacks.
JvJava
import java.util.Arrays;
int[] a = {1, 3, 3, 5, 7};
int hit = Arrays.binarySearch(a, 3); // 1 — SOME index within the 3s
int miss = Arrays.binarySearch(a, 4); // -3 — encodes insertion point 2
if (hit < 0) {
int insertion = -hit - 1; // decode: 2
}Absent is negative: -(insertion) - 1, so a valid index 0 is never ambiguous; decode with -r - 1. It is only correct on SORTED arrays — unsorted input returns garbage WITHOUT throwing (undefined behavior, not an exception), and with duplicates which index you get is unspecified.
SwSwift
func lowerBound(_ a: [Int], _ target: Int) -> Int {
var lo = 0, hi = a.count // half-open [lo, hi)
while lo < hi {
let mid = lo + (hi - lo) / 2 // overflow-safe midpoint
if a[mid] < target { lo = mid + 1 }
else { hi = mid }
}
return lo // the index, or the insertion point
}
let a = [1, 3, 3, 5, 7]
lowerBound(a, 3) // 1
lowerBound(a, 4) // 2 — absent: where 4 insertsNo stdlib binary search — firstIndex(of:) is a linear scan. lo + (hi - lo) / 2, never (lo + hi) / 2: Swift TRAPS (crashes) on signed-integer overflow instead of wrapping, so the naive midpoint is a loud crash on huge arrays rather than the quiet wrong answer it is in C.
KtKotlin
val a = intArrayOf(1, 3, 3, 5, 7)
val hit = a.binarySearch(3) // 1 — some index within the 3s
val miss = a.binarySearch(4) // -3 — -(insertion) - 1, the JVM encoding
val ins = -(miss + 1) // 2
// slice overload — searches [fromIndex, toIndex) without copying:
val hit2 = a.binarySearch(3, 0, 3)
check(ins in 0..a.size) // invariant: the decoded slot is insertableSame JVM Arrays.binarySearch underneath — the -(ins)-1 encoding and the sorted-input requirement come with it, verified by nothing. The fromIndex/toIndex overload searches a slice in place; Kotlin's check()/require() are where the invariants finally get stated.
RbRuby
a = [1, 3, 3, 5, 7]
# find mode — boolean block, returns the ELEMENT (or nil):
elem = a.bsearch { |x| x >= 3 } # => 3
# find-index mode — <=> block, returns the INDEX (or nil):
idx = a.bsearch { |x| (x <=> 3) } # => 1, the leftmost equal
# no insertion point from bsearch — count is O(n), hand-roll for hot paths:
ins = a.count { |x| x < 4 } # => 2The block's RETURN TYPE selects the mode: boolean → find mode (the element or nil), three-way <=> → find-index mode (the leftmost index or nil). A one-token difference changes the return shape entirely — and neither mode gives the insertion point (count { } is linear; hand-roll when it matters).
ZigZig
const std = @import("std");
/// Smallest i where items[i] >= key — the insertion point.
/// std.sort.binarySearch cannot answer this: it yields ?usize, presence only.
fn lowerBound(items: []const i32, key: i32) usize {
var lo: usize = 0;
var hi: usize = items.len; // half-open [lo, hi)
while (lo < hi) {
const mid = lo + (hi - lo) / 2; // overflow-safe midpoint
switch (std.math.order(items[mid], key)) {
.lt => lo = mid + 1,
else => hi = mid, // .eq and .gt: mid stays a candidate
}
}
return lo;
}std.sort.binarySearch returns ?usize — an index or null, PRESENCE only; it does NOT give the insertion point, so the lowerBound variant is hand-rolled (its comparator answers std.math.Order). Same overflow-safe lo + (hi - lo) / 2 discipline as every other language here.