Drcus | 王亚振

Drcus | 王亚振

随便写,记录点东西

JS-二分查找

发布于:  

用 JavaScript 实现二分查找

二分查找的基本过程步骤:

  1. 选择数组的中间值
  2. 如果选中值是待搜索值,算法结束(找到了)
  3. 如果待搜索值比选中值大,则返回步骤1并在选中值右边子数组中查找
  4. 如果待搜索值比选中值小,则返回步骤1并在选中值左边子数组中查找
Array.prototype.binarySearch = function(item) {
  let low = 0
  let high = this.length - 1
  let mid = null
  let element = null
  
  while (low <= high) {
    mid = Math.floor((high + low) / 2)
    element = this[mid]
    if (element < item) {
      low = mid + 1    
    } else if (element > item) {
      high = mid - 1
    } else {
      return mid
    }
  }
  return - 1
}

~^_^~ 一片小花园 ?

赏赐