第90题 实现二分查找并分析时间复杂度

思路分析

二分查找，每次都取1/2，缩小范围，直到找到那个数为止

• 递归，代码逻辑更加清晰
• 非递归，性能更好
• 二分查找时间复杂度 O(logn) 非常快

总结

• 只要是可排序的，都可以用二分查找
• 只要用二分的思想，时间复杂度必包含O(logn)

二分查找（循环）

    /**
     * 二分查找（循环）
     * @param arr arr:number[]
     * @param target target:number 查找的目标值的索引
     */
    function binarySearch1(arr, target) {
      const length = arr.length
      if (length === 0) return -1 // 找不到
    
      // ![](https://s.poetries.work/uploads/2023/01/2f43f28ec7699c17.png)
      // startIndex、endIndex当前查找区域的开始和结束
      let startIndex = 0 // 查找的开始位置
      let endIndex = length - 1 // 查找的结束位置
    
      // startIndex和endIndex还没有相交，还是有查找的范围的
      while (startIndex <= endIndex) {
        const midIndex = Math.floor((startIndex + endIndex) / 2)
        const midValue = arr[midIndex] // 获取中间值
        if (target < midValue) { // 查找的目标值小于中间值
          // 目标值较小，则继续在左侧查找
          endIndex = midIndex - 1
        } else if (target > midValue) { // 查找的目标值大于中间值
          // 目标值较大，则继续在右侧查找
          startIndex = midIndex + 1
        } else {
          // 相等，返回目标值的索引
          return midIndex
        }
      }
    
      return -1 // startIndex和endIndex相交后还是找不到返回-1
    }

二分查找（递归）

    /**
     * 二分查找（递归）
     * @param arr arr:number[]
     * @param target target:number 查找的目标值的索引
     * @param startIndex?:number start index 二分查找区间的开始位置
     * @param endIndex?:number end index 二分查找区间的结束位置
     */
    function binarySearch2(arr, target, startIndex, endIndex) {
      const length = arr.length
      if (length === 0) return -1
    
      // 开始和结束的范围
      if (startIndex == null) startIndex = 0
      if (endIndex == null) endIndex = length - 1
    
      // 如果 start 和 end 相遇，则结束
      if (startIndex > endIndex) return -1
    
      // 中间位置
      const midIndex = Math.floor((startIndex + endIndex) / 2)
      const midValue = arr[midIndex] // 中间值
    
      if (target < midValue) {
        // 目标值较小，则继续在左侧查找 endIndex = midIndex - 1 往左移动一点
        return binarySearch2(arr, target, startIndex, midIndex - 1)
      } else if (target > midValue) {
        // 目标值较大，则继续在右侧查找 startIndex = midIndex + 1 往右移动一点
        return binarySearch2(arr, target, midIndex + 1, endIndex)
      } else {
        // 相等，返回
        return midIndex
      }
    }

    // 功能测试
    const arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120]
    const target = 40
    console.info(binarySearch2(arr, target))

    // 性能测试
    
    // 二分查找（循环）
    console.time('binarySearch1')
    for (let i = 0; i < 100 * 10000; i++) {
      binarySearch1(arr, target)
    }
    console.timeEnd('binarySearch1') // 17ms
    
    // 二分查找（递归）
    console.time('binarySearch2')
    for (let i = 0; i < 100 * 10000; i++) {
      binarySearch2(arr, target)
    }
    console.timeEnd('binarySearch2') // 34ms
    
    // 结论：二分查找（循环）比二分查找（递归）性能更好，递归过程多次调用函数导致性能慢一点