二分搜索

在计算机科学中，二分搜索（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

注意：二分搜索只能从已排序的数组中进行搜索。

实现

有两种方法实现二分搜索，一种是递归，一种是迭代。

递归法

function binarySearch(arr, value) {
  function search(arr, start, end, value) {
    if(start > end) {
      return -1
    }
    let mid = parseInt((start + end)/2)
    if(arr[mid] > value) {
      return search(arr, start, mid - 1, value)
    } else if(arr[mid] < value) {
      return search(arr, mid + 1, end, value)
    } else {
      return mid
    } 
  }
  return search(arr, 0, arr.length-1, value)
}

迭代法

function binarySearch(arr, value) {
  let [start, end] = [0, arr.length - 1]
  let mid
  while(start <= end) {
    mid = parseInt((start + end)/2)
    if(arr[mid] < value) {
      start = mid + 1
    } else if(arr[mid] > value) {
      end = mid - 1
    } else {
      return mid
    }
  }
  return -1
}

复杂度

时间复杂度：O(logn)

空间复杂度：

• 迭代： O(1)
• 递归： O(logn)

参考

• wiki-二分搜索算法