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

简介: 如何使用JS实现一个合格的二分查找

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

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

相关文章
|
4天前
|
算法 程序员 数据处理
算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解
算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解
|
7天前
|
人工智能 算法 测试技术
【动态规划】【二分查找】C++算法 466 统计重复个数
【动态规划】【二分查找】C++算法 466 统计重复个数
|
2天前
|
Rust 前端开发 JavaScript
前端技术的未来:WebAssembly与JavaScript的融合之路
【2月更文挑战第12天】本文旨在探讨WebAssembly(以下简称Wasm)与JavaScript(以下简称JS)的结合如何为前端开发带来革命性变化。传统上,JS一直是前端开发的核心,但随着Wasm的出现,我们看到了前端性能和功能的新天地。文章首先介绍Wasm的基本概念,然后分析其对前端开发的影响,包括性能提升、新功能实现以及开发模式的变化。最后,探讨了Wasm与JS融合的未来趋势,以及这种融合如何推动前端技术的进步。
|
2天前
|
Rust 前端开发 JavaScript
探索前端技术的未来:WebAssembly与JavaScript的融合之路
【2月更文挑战第12天】 随着Web技术的不断进步,前端开发正迎来一场革命性变革。本文将深入探讨WebAssembly(以下简称Wasm)与JavaScript(以下简称JS)的结合如何为前端开发带来前所未有的性能提升与新的编程模式。我们将从两者的基本概念入手,探索它们各自的优势与局限,然后深入分析Wasm和JS协同工作时能够解锁的潜力,最后展望这一技术趋势如何塑造未来的前端开发生态。本文旨在为前端开发者提供洞见,帮助他们理解并准备好迎接这一即将到来的技术浪潮。
|
2天前
|
Rust 前端开发 JavaScript
前端技术的未来演进:WebAssembly与JavaScript的深度融合
【2月更文挑战第11天】 在数字化时代,前端技术的迅速发展不仅推动了用户体验的革新,也促进了Web应用的性能提升。本文将探讨WebAssembly(以下简称Wasm)与JavaScript(以下简称JS)之间的深度融合如何成为前端技术发展的关键转折点。不同于传统的技术文章摘要,我们将通过一种叙事式的预览引导读者进入这一技术领域的探索之旅,揭示Wasm和JS结合后为前端开发带来的无限可能性和挑战。
|
6天前
|
人工智能 JavaScript 前端开发
前端秘法基础式终章----欢迎来到JS的世界
前端秘法基础式终章----欢迎来到JS的世界
|
6天前
|
机器学习/深度学习 算法 Java
【数据结构查找算法篇】----二分查找【实战项目】
【数据结构查找算法篇】----二分查找【实战项目】
14 1
|
7天前
|
JavaScript 前端开发 算法
【Node.js 版本过高】运行前端时,遇到错误 `Error: error:0308010C:digital envelope routines::unsupported`
【Node.js 版本过高】运行前端时,遇到错误 `Error: error:0308010C:digital envelope routines::unsupported`
15 0
|
7天前
|
算法 测试技术 C++
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
【KMP】【二分查找】【C++算法】100207. 找出数组中的美丽下标 II
|
7天前
|
算法 测试技术 C++
【位运算】【二分查找】【C++算法】100160价值和小于等于 K 的最大数字
【位运算】【二分查找】【C++算法】100160价值和小于等于 K 的最大数字

相关产品

  • 云迁移中心