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)))
斐波那契查找
也是二分查找的一种提升算法,斐波那契查找也属于一种有序查找算法。