搜索算法

顺序搜索

时间复杂度：O(n)

原理

将数组中的每一项与要找的元素做比较。

实现

function sequentialSearch(arr, item) {
  for (var i = 0; i < arr.length; i++) {
    if (item === arr[i]) {
      return i
    }
  }
  return -1
}

二分搜索

时间复杂度：O(log(n))

原理

先对数组排序，选择中间项为主元，要搜索的元素比主元大在右边寻找，比主元小在左边寻找，再选择剩余部分的中间项为主元，直到找到要找的元素。

实现

function binarySearch(arr, item) {
  quickSort(arr) //先进行快速排序

  var low = 0,
    high = arr.length - 1,
    mid,
    element

  while (low <= high) {
    mid = Math.floor(arr.length / 2)
    element = arr[mid]
    if (element < item) {
      low = mid + 1
    } else if (element > item) {
      high = mid - 1
    } else {
      return mid
    }
  }
  return -1
}