JavaScript数据结构与算法(搜索算法)

顺序搜索

最基本的搜索算法，最低效的一种搜索算法。它的机制是，将每一个数据结构中的元素和要找的元素做比较。

function search(array, value) {
  for (let i = 0; i < array.length; i++) {
    if (value === array[i]) {
      return i
    }
  }
  return -1
}

console.log(search([1, 3, 5, 2, 0], 5))

二分搜索

这个算法要求被搜索的数据结构已排序。

function binarySearch(find, arr, start, end) {
  start = start || 0
  end = end || arr.length - 1

  if (start <= end && find >= arr[start] && find <= arr[end]) {
    if (arr[start] === find) {
      return start
    }
    if (arr[end] === find) {
      return end
    }

    let mid = Math.ceil((end + start) / 2)
    if (arr[mid] === find) {
      return mid
    } else if (arr[mid] > find) {
      return binarySearch(find, arr, start, mid - 1)
    } else {
      return binarySearch(find, arr, mid + 1, end)
    }
  }

  return -1
}

function quickSort(arr) {
  const { length } = arr
  if (length < 2) {
    return arr
  }

  let base = arr[0]
  let minArr = arr.slice(1).filter((item) => item <= base)
  let maxArr = arr.slice(1).filter((item) => item > base)

  return quickSort(minArr).concat(base).concat(quickSort(maxArr))
}

arr = quickSort([1, 3, 5, 2, 0])

console.log(...arr)
console.log(binarySearch(2, arr))

内插搜索

是改良版的二分搜索，只需改动mid：

let mid = (start + Math.floor(((find - arr[start]) / (arr[end] - arr[start])) * (end - start)))

斐波那契查找

也是二分查找的一种提升算法，斐波那契查找也属于一种有序查找算法。