美文网首页
前端-二分查找

前端-二分查找

作者: FConfidence | 来源:发表于2018-09-07 23:52 被阅读6次
/**
 * [binarySeach 二分查找]
 * @param  {[Array]} arr    [待查找的有序数组]
 * @param  {[Number|String]} target [查找的目标元素]
 * @return {[Integer]}        [description]
 */
function binarySeach(arr, target) {
  let low = 0,
    high = arr.length - 1;
  while (low <= high) { // 在low <= high 区间 仍然是有元素的
    const mid = parseInt((low + high) / 2); // 考虑整型溢出的情况  mid = low + parseInt((high - low)/2)
    if (arr[mid] === target) {
      return mid;
    }
    if (arr[mid] < target) {
      low = mid + 1; // target在 [mid+1, high]
    } else {
      high = mid - 1; // // target在 [low, mid-1]
    }
  } // end while
  // 元素不存在的时候
  return -1;
}

const arr = [0, 1, 2, 3, 4, 5, 6, 8, 9, 10]
console.log(binarySeach(arr, 7))
console.log(binarySeach(arr, 6))
console.log(binarySeach(arr, 1))
console.log(binarySeach(arr, 10))
console.log(binarySeach(arr, 0))

相关文章

网友评论

      本文标题:前端-二分查找

      本文链接:https://www.haomeiwen.com/subject/hxzhgftx.html