用js实现二分查找

题目如下

• 用js实现二分查找

思路如下

• 通过循环
• 通过递归

/**
 * @description 二分查找
 * @author sola-grj
 */

/**
 * 二分查找（循环）
 * @param arr arr
 * @param target target
 */

export function binarySearch1(arr:number[],target:number):number {
  const length = arr.length
  if(length === 0) return -1
  
  let startIndex = 0 // 开始位置
  let endIndex = length - 1 // 结束位置
  
  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
}

/**
 * 二分查找（递归）
 * @param arr arr
 * @param target target
 * @param startIndex start index
 * @param endIndex end index
 */
export function binarySearch2(arr: number[], target: number, startIndex?: number, endIndex?: number): number {
  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){
    // 目标较小，继续在左侧查找
    return binarySearch2(arr,target,startIndex,midIndex - 1)
  }else if (target > midValue) {
    return binarySearch2(arr,target,midIndex + 1,endIndex)
  }else {
    // 相等 返回
    return midIndex
  }
}

// 性能测试 递归性能
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

单元测试

/**
 * @description 二分查找 test
 * @author 双越老师
 */

import { binarySearch1, binarySearch2 } from './binary-search'

describe('二分查找', () => {
    it('正常情况', () => {
        const arr = [10, 20, 30, 40, 50]
        const target = 40
        const index = binarySearch1(arr, target)
        expect(index).toBe(3)
    })

    it('空数组', () => {
        expect(binarySearch1([], 100)).toBe(-1)
    })

    it('找不到 target', () => {
        const arr = [10, 20, 30, 40, 50]
        const target = 400
        const index = binarySearch1(arr, target)
        expect(index).toBe(-1)
    })
})