Algorithms: Searching

def binary_search(a: list[int], target: int) -> int:
    alg_require(isinstance(a, (list, tuple)) and len(a) <= 1000000)
    alg_require(type(target) is int and -2147483648 <= target <= 2147483647)
    n: int = len(a)
    alg_require(n >= 0 and n <= 1000000)
    alg_require(len(a) == n)
    lo: int = 0
    hi: int = n - 1
    mid: int = 0
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:

int binary_search(const int *a, size_t a_length, int target) {
    int alg_error = 0;
    int alg_result = INT_MIN;
    errno = 0;
    if (a_length > 1000000 || (a_length && !a)) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    int n = (int)a_length;
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((n >= 0) && (n <= 1000000)))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    if (!(((int)a_length == n))) { errno = EINVAL; alg_result = INT_MIN; goto alg_cleanup; }
    if (alg_error) { errno = ERANGE; alg_result = INT_MIN; goto alg_cleanup; }
    int lo = 0;

int binary_search(const std::vector<int>& a, int target) {
    alg_require(a.size() <= 1000000);
    int n = (int)a.size();
    alg_require(((n >= 0) && (n <= 1000000)));
    alg_require(((int)a.size() == n));
    int lo = 0;
    int hi = alg_sub(n, 1);
    int mid = 0;
    while ((lo <= hi)) {
        mid = alg_add(lo, (alg_sub(hi, lo) / 2));
        if ((a[mid] == target)) {
            return mid;

    static int binary_search(ReadOnlySpan<int> a, int target) {
        checked {
            int n = a.Length;
            alg_require(((n >= 0) && (n <= 1000000)));
            alg_require((a.Length == n));
            int lo = 0;
            int hi = (n - 1);
            int mid = 0;
            while ((lo <= hi)) {
                mid = (lo + ((hi - lo) / 2));
                if ((a[mid] == target)) {
                    return mid;

function binary_search(array $a, int $target): int {
    alg_require(array_is_list($a));
    $n = count($a);
    alg_require((($n >= 0) && ($n <= 1000000)));
    alg_require((count($a) == $n));
    $lo = 0;
    $hi = alg_sub($n, 1);
    $mid = 0;
    while (($lo <= $hi)) {
        $mid = alg_add($lo, intdiv(alg_sub($hi, $lo), 2));
        if (($a[$mid] == $target)) {
            return $mid;