Recherche binaire : indice, point d'insertion ou présence snippet

// 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 take

// 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 point

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 })

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 sibling

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
}

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) shift

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 */ }

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
}

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 inserts

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 insertable

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 }             # => 2

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;
}