二分法

前提:数组已预先排序。 目标:查找数组中指定数字的坐标(0-based)。

二分法通俗点说,就是对一个已经事先排序过的数组,设置分别指向数组首尾两头的首尾游标,然后根据首尾游标的位置设定中间点游标,由于数组已经排序过了,可以通过比较给定数字与三个游标的大小关系来不断的更新首尾中三个游标的位置,这个过程中只要收尾中三个游标对应的数字有一个等于给定数字,或者首尾游标的位置中间仅剩一个游标位,就可以拿到给定数字对应的位置的。

function binarySearch (arr, num) {
  // assume arr has been sorted in advance
  var low = 0
  var high = arr.length - 1
  var mid = Math.floor((low + high) / 2)

  // 循环的终止条件是high - low长度等于1,或遍历期间直接取到了目标数字
  // 因为目标是找到指定数字在原数组中的下标,所以采用递归拆数组的思路反而不方便
  while (high - low > 1) {
    if (num === arr[low]) {
      return low
    } else if (num === arr[high]) {
      return high
    } else if (num === arr[mid]) {
      return mid
    } else if (num > arr[mid]) {
      low = mid
      mid = Math.floor((low + high) / 2)
    } else {
      high = mid
      mid = Math.floor((low + high) / 2)
    }
  }

  // if not found
  return -1
}

 

Author: Yakima
关于作者:楠溪江人,出生于1991年,目前坐标上海。读书时代跳过级、保过送,工作后转过行。2013年本科毕业于北药。看书、码字、敲代码、打羽毛球是我花时间的爱好。曾在某上市药企任国际药品注册岗,现在某高新企业任前端管理岗。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据