【前端算法】javaScript实现二分查找

JS实现二分查找

• 递归- 代码逻辑更清晰
• 非递归- 性能更好
• 时间复杂度O(logn) ——非常快！

代码实现 —— 循环

function binarySearch1(arr: number[], sval: number): number {
  const len = arr.length
  if (len === 0) return -1

  let startIdx = 0 // 开始位置
  let endIdx = len - 1 // 结束位置

  while (startIdx <= endIdx) {
    let midIdx = Math.floor((startIdx + endIdx) / 2)
    let midVal = arr[midIdx] // 中间值

    if (sval < midVal) {
      // 小于中间值，继续在左侧寻找
      endIdx = midIdx - 1
    } else if (sval > midVal) {
      // 大于中间值，继续在右侧寻找
      startIdx = midIdx + 1
    } else {
      // 等于中间值
      return midIdx
    }
  }
  return -1
}

代码实现 —— 递归

function binarySearch2(arr: number[],target: number, startIdx?: number, endIdx?: number): number {
  const len = arr.length
  if (len === 0) return -1

  // 初始化边界
  if (typeof startIdx !== 'number') startIdx = 0
  if (typeof endIdx !== 'number') endIdx = len - 1

  const midIdx = Math.floor((startIdx + endIdx) / 2)

  if (startIdx > endIdx) return -1
  // 开始比较
  if (target < arr[midIdx]) {
    // 小于中间值，继续在左侧寻找
    return binarySearch2(arr, target, startIdx, midIdx - 1)
  } else if (target > arr[midIdx]) {
    // 大于中间值，继续在右侧寻找
    return binarySearch2(arr, target, midIdx + 1, endIdx)
  } else {
    // 等于中间值
    return midIdx
  }
}

功能测试

const arr = [1, 4, 6, 8, 9, 11, 14, 19, 21, 22, 31, 32, 35, 36, 40, 50, 80, 100, 120]
const res:number = binarySearch1(arr,9) // 4
const res:number = binarySearch2(arr,9) // 4

单元测试

describe('二分查找' , () => {
  it('正常情况',() => {
    const arr = [1, 4, 6, 8, 9, 11, 14, 19, 21, 22, 31, 32, 35, 36, 40, 50, 80, 100, 120]
    const res:number = binarySearch1(arr,9)
    expect(res).toBe(4)
  })

  it('空数组', () => {
    const res:number = binarySearch1([],9)
    expect(res).toBe(-1)
  })

  it('找不到 target', () => {
    const arr = [1, 4, 6, 8, 9, 11, 14, 19, 21, 22, 31, 32, 35, 36, 40, 50, 80, 100, 120]
    const res:number = binarySearch1(arr,51)
    expect(res).toBe(-1)
  })
})

性能比较

const arr = [1, 4, 6, 8, 9, 11, 14, 19, 21, 22, 31, 32, 35, 36, 40, 50, 80, 100, 120]
console.time('binarySearch1')
for (let j = 0; j < 100 * 10000; j++) {
  const res = binarySearch1(arr, 50)
}

console.timeEnd('binarySearch1')

console.time('binarySearch2')
for (let j = 0; j < 100 * 10000; j++) {
  const res = binarySearch2(arr, 50)
}

console.timeEnd('binarySearch2')

打印结果

binarySearch1: 15.719ms
binarySearch2: 33.577ms

由此可见循环的二分比递归的二分，性能更佳，但是递归语义更容易理解，所以常用的还是递归！