二分查找法

CREATE: 2022-03-11 22:14:09

题目：实现一个二分查找的功能 ( 简单😄 )

给定一个有序数组 s，请找出数字 t 的位置，请利用 Ts | Js，实现一个二分查找的功能

分析

• 遍历：时间复杂度 O(n)
• 二分法：时间复杂度 O(logn)

可以从图中看到，logn 复杂度到后续越来越快（因为区间越来越小）

题解

function binarySearch(s?: number[], t?: number) {
  if (!s || t == undefined) {
    return
  }

  let l = 0,
    r = s.length - 1

  while (l < r) {
    const mid = Math.floor((r + l + 1) / 2)

    if (t === s[l] || t === s[r]) {
      return t === s[l] ? l : r
    }

    if (t === s[mid]) {
      return mid
    } else if (t > s[mid]) {
      l = mid + 1
    } else {
      r = mid
    }
  }

  return undefined
}

使用

function main() {
  const s = [2, 3, 5, 7, 11, 13, 17]
  const t = 11

  console.log('[]:', binarySearch(s, t))
}

main()