二分查找

function mySqrt(x: number): number {
    let [a, b] = [0, x]
    while (a <= b) {
        let m = Math.floor((a + b) / 2)
        if (m * m < x) a = m + 1
        else if (m * m > x) b = m - 1
        else return m
    }
    return b
};

function nextGreatestLetter(letters: string[], target: string): string {
    let [a, b] = [0, letters.length - 1]
    while (a <= b) {
        let m = Math.floor((a + b) / 2)
        if (letters[m] <= target) a = m + 1
        else b = m - 1
    }
    return a === letters.length ? letters[0] : letters[a]
};

function singleNonDuplicate(nums: number[]): number {
    function lessthan(i) {
        return i % 2 === 0
            ? nums[i] === nums[i + 1]
            : nums[i] === nums[i - 1]
    }
 
    let [a, b] = [0, nums.length - 1]
    while (a <= b) {
        let m = Math.floor((a + b) / 2)
        if (lessthan(m)) a = m + 1
        else b = m - 1
    }
    return nums[a]
};

var solution = function(isBadVersion: any) {
 
    return function(n: number): number {
        let [a, b] = [1, n]
        while (a <= b) {
            let m = Math.floor((a + b) / 2)
            if (!isBadVersion(m)) a = m + 1
            else b = m - 1
        }
        return a
    };
};

function findMin(nums: number[]): number {
    function lessthan(i) {
        return nums[i] > nums.at(-1)
    }
 
    let [a, b] = [0, nums.length - 1]
    while (a <= b) {
        let m = Math.floor((a + b) / 2)
        if (lessthan(m)) a = m + 1
        else b = m - 1
    }
    return nums[a]
};

function searchRange(nums: number[], target: number): number[] {
    function bs(x) {
        let [a, b] = [0, nums.length - 1]
        while (a <= b) {
            let m = Math.floor((a + b) / 2)
            if (nums[m] < x) a = m + 1
            else b = m - 1
        }
        return a
    }
 
    let [a, b] = [bs(target), bs(target + 1) - 1]
    if (nums[a] === target && nums[b] === target) {
        return [a, b]
    } else {
        return [-1, -1]
    }
};