/**
 * 解法一:循环
 * 思路:
 * (1)从数组首尾开始,每次取中点值。
 * (2)如果中间值等于目标即找到了,可返回下标,如果中点值大于目标,
 *  说明中点以后的都大于目标,因此目标在中点左半区间,如果中点值小于目标,则相反。
 * (3)根据比较进入对应的区间,直到区间左右端相遇,意味着没有找到。
 * 时间复杂度:O(log2n),对长度为n的数组进行二分,最坏情况就是取2的对数
 * 空间复杂度:0(1),无额外空间
 */
export function search(nums: number[], target: number): number {
    const len = nums.length
    if (len === 0) return -1

    let startIndex = 0
    let endIndex = len - 1

    while (startIndex <= endIndex) {
        const midIndex = Math.floor((startIndex + endIndex) / 2) // 将数字向下舍入到最接近的整数
        const midValue = nums[midIndex]

        if (target < midValue) {
            // 目标值较少,则继续在左侧查找 
            endIndex = midIndex - 1
        } else if (target > midValue) {
            // 目标值较大,则继续在右侧查找 
            startIndex = midIndex + 1
        } else {
            return midIndex
        }
    }

    return -1
};

/**
 * 解法二:递归
 * 思路:
 * (1)从数组首尾开始,每次取中点值。
 * (2)如果中间值等于目标即找到了,可返回下标,如果中点值大于目标,说明中点以后的都大于目标,
 *  因此目标在中点左半区间,如果中点值小于目标,则相反。
 * (3)根据比较进入对应的区间,直到区间左右端相遇,意味着没有找到。
 * 时间复杂度:O(logn),对长度为n的数组进行二分,最坏情况就是取2的对数
 * 空间复杂度:0(1)
 */
 function search(nums: number[], target: number, startIndex?: number, endIndex?: number): number {
    const len = nums.length;
    if (len === 0) return -1;

    // 开始和结束的范围
    if (startIndex == null) startIndex = 0
    if (endIndex == null) endIndex = len - 1

    // 如果 start 和 end 相遇则结束
    if (startIndex > endIndex) return -1

    // 中间位置
    const midIndex = Math.floor((startIndex + endIndex) / 2)
    const midValue = nums[midIndex]

    if (target < midValue) {
        // 目标值较小,则继续在左侧查找
        return search(nums, target, startIndex, midIndex - 1)
    } else if (target > midValue) {
        // 目标值较大,则继续在右侧查找
        return search(nums, target, midIndex + 1, endIndex)
    } else {
        // 相等,返回
        return midIndex
    }
};

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview