Tìm kiếm nhị phân (Binary Search)

// Binary search on an array sorted in ascending order.
// Every step looks at the middle of the range that can still hold the answer
// and throws away the half that cannot — so n items take about log2(n) steps.

/**
 * Finds `target` in `sorted`.
 * With duplicates it returns one of the matching indexes, not necessarily the first —
 * use `lowerBound` when you need the first one.
 *
 * @param {number[]} sorted values in ascending order
 * @param {number} target the value to look for
 * @returns {number} an index i with sorted[i] === target, or -1 if there is none
 */
export function binarySearch(sorted, target) {
  let lo = 0;
  let hi = sorted.length - 1; // the answer, if any, is inside [lo, hi] (both ends included)

  while (lo <= hi) {
    // Same as (lo + hi) / 2, but lo + hi can overflow a fixed-size integer in other languages.
    const mid = lo + Math.floor((hi - lo) / 2);

    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) {
      lo = mid + 1; // sorted[lo..mid] are all too small
    } else {
      hi = mid - 1; // sorted[mid..hi] are all too big
    }
  }
  return -1; // the range is empty: target is not in the array
}

/**
 * The first index whose value is >= `target` — where `target` would be inserted to keep the
 * array sorted. Returns `sorted.length` when every value is smaller than `target`.
 *
 * @param {number[]} sorted values in ascending order
 * @param {number} target the value to look for
 * @returns {number} an index in [0, sorted.length]
 */
export function lowerBound(sorted, target) {
  let lo = 0;
  let hi = sorted.length; // the answer is inside [lo, hi) — hi itself is a valid answer

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);

    if (sorted[mid] < target) {
      lo = mid + 1; // mid and everything before it are too small
    } else {
      hi = mid; // mid might be the answer, so keep it in the range
    }
  }
  return lo; // lo === hi: the first index whose value is >= target
}

# Binary search on a list sorted in ascending order.
# Every step looks at the middle of the range that can still hold the answer
# and throws away the half that cannot — so n items take about log2(n) steps.
from typing import Sequence


def binary_search(sorted_values: Sequence[int], target: int) -> int:
    """Return an index i with sorted_values[i] == target, or -1 if there is none.

    With duplicates it returns one of the matching indexes, not necessarily
    the first — use lower_bound when you need the first one.
    """
    lo = 0
    hi = len(sorted_values) - 1  # the answer, if any, is inside [lo, hi] (both ends included)

    while lo <= hi:
        # Python integers never overflow, but this form is safe in every language.
        mid = lo + (hi - lo) // 2

        if sorted_values[mid] == target:
            return mid
        if sorted_values[mid] < target:
            lo = mid + 1  # sorted_values[lo..mid] are all too small
        else:
            hi = mid - 1  # sorted_values[mid..hi] are all too big
    return -1  # the range is empty: target is not in the list


def lower_bound(sorted_values: Sequence[int], target: int) -> int:
    """Return the first index whose value is >= target.

    That is where target would be inserted to keep the list sorted, so it is
    len(sorted_values) when every value is smaller (same as bisect.bisect_left).
    """
    lo = 0
    hi = len(sorted_values)  # the answer is inside [lo, hi) — hi itself is a valid answer

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if sorted_values[mid] < target:
            lo = mid + 1  # mid and everything before it are too small
        else:
            hi = mid  # mid might be the answer, so keep it in the range
    return lo  # lo == hi: the first index whose value is >= target

/**
 * Binary search on an array sorted in ascending order.
 * Every step looks at the middle of the range that can still hold the answer
 * and throws away the half that cannot — so n items take about log2(n) steps.
 */
public final class BinarySearch {
    private BinarySearch() {
    }

    /**
     * Returns an index i with sorted[i] == target, or -1 if there is none.
     * With duplicates it returns one of the matching indexes, not necessarily the first —
     * use {@link #lowerBound} when you need the first one.
     */
    public static int binarySearch(int[] sorted, int target) {
        int lo = 0;
        int hi = sorted.length - 1; // the answer, if any, is inside [lo, hi] (both ends included)

        while (lo <= hi) {
            // (lo + hi) / 2 overflows when lo + hi > Integer.MAX_VALUE; this form never does.
            int mid = lo + (hi - lo) / 2;

            if (sorted[mid] == target) {
                return mid;
            }
            if (sorted[mid] < target) {
                lo = mid + 1; // sorted[lo..mid] are all too small
            } else {
                hi = mid - 1; // sorted[mid..hi] are all too big
            }
        }
        return -1; // the range is empty: target is not in the array
    }

    /**
     * Returns the first index whose value is >= target — where target would be inserted to keep
     * the array sorted. Returns sorted.length when every value is smaller than target.
     */
    public static int lowerBound(int[] sorted, int target) {
        int lo = 0;
        int hi = sorted.length; // the answer is inside [lo, hi) — hi itself is a valid answer

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;

            if (sorted[mid] < target) {
                lo = mid + 1; // mid and everything before it are too small
            } else {
                hi = mid; // mid might be the answer, so keep it in the range
            }
        }
        return lo; // lo == hi: the first index whose value is >= target
    }
}

// Binary search on a vector sorted in ascending order.
// Every step looks at the middle of the range that can still hold the answer
// and throws away the half that cannot — so n items take about log2(n) steps.
// (The standard library has it too: std::binary_search and std::lower_bound in <algorithm>.)
#include <vector>

// Returns an index i with sorted[i] == target, or -1 if there is none.
// With duplicates it returns one of the matching indexes, not necessarily the first —
// use lowerBound when you need the first one.
int binarySearch(const std::vector<int>& sorted, int target) {
    int lo = 0;
    int hi = static_cast<int>(sorted.size()) - 1;  // the answer, if any, is inside [lo, hi]

    while (lo <= hi) {
        // (lo + hi) / 2 overflows when lo + hi > INT_MAX; this form never does.
        int mid = lo + (hi - lo) / 2;

        if (sorted[mid] == target) {
            return mid;
        }
        if (sorted[mid] < target) {
            lo = mid + 1;  // sorted[lo..mid] are all too small
        } else {
            hi = mid - 1;  // sorted[mid..hi] are all too big
        }
    }
    return -1;  // the range is empty: target is not in the vector
}

// Returns the first index whose value is >= target — where target would be inserted to keep
// the vector sorted. Returns sorted.size() when every value is smaller than target.
int lowerBound(const std::vector<int>& sorted, int target) {
    int lo = 0;
    int hi = static_cast<int>(sorted.size());  // the answer is inside [lo, hi) — hi itself is valid

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (sorted[mid] < target) {
            lo = mid + 1;  // mid and everything before it are too small
        } else {
            hi = mid;  // mid might be the answer, so keep it in the range
        }
    }
    return lo;  // lo == hi: the first index whose value is >= target
}