线性搜索
一种寻找某一特定的搜索算法
按一定的顺序检查数组中每一个元素，直到找到想要找的特定值为止。
function linearSearch(arr, value){
for(let i= 0; i < arr.length; i++){
if(arr[i] === value){
return i
}
}
return -1
}
线性搜索优化
28原则
function linearSearch(arr, value){
for(let i=0; i<arr.length; i++){
if(arr[i] === value){
if(i>0){
[arr[i-1],arr[i]] = [arr[i],arr[i-1]]
}
return i
}
}
return -1 //表示没有找到，最小只有第0，
}
查找最大（小）值
- 将数组的第0项作为最小值
- 依次拿数组的剩余项和最小值作比较
if(arr[i]< min){
min = arr[i]
}
arr.indexOf(value) // 下标
arr.find(val => val === value) //获取值
Math.max.apply(null, arr) //旧写法
Math.max(...[arr]) //ES6写法
二分搜索
一种在有序数组中查找某一特定元素的搜索算法，搜索过程从数组的中间元素开始，
只能从已排序的数组中进行搜索
递归法
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){
start = mid - 1
}else {
return mid
}
}
return -1
}
广度优先搜索
Breadth-First-Search
从根节点开始，沿着树的宽度遍历树的节点。如果所有节点都被访问，则算法中止。
class Node{
constructor(data){
this.data = data
this.children = []
this.parent = null
}
insertChild(child){
this.children.push(child)
child.setParent(this)
}
setParent(parent){
this.parent = parent
}
}
let node0 = new Node(0)
let node1 = new Node(1)
let node2 = new Node(2)
let node3 = new Node('hello')
let node4 = new Node(4)
let node5 = new Node(5)
node0.insertChild(node1)
node0.insertChild(node2)
node1.insertChild(node3)
node1.insertChild(node4)
node2.insertChild(node5)
function bfsSearch(root,value){
let list = []
let target
list.push(root)
while(list.length){
target = list.shift()
if(target.data === value) return value
list.push(...target.children)
}
}
深度优先搜索
Depth-First-Search
class Node{
constructor(data){
this.data = data
this.children = []
this.parent = null
}
insertChild(child){
this.children.push(child)
child.setParent(this)
}
setParent(parent){
this.parent = parent
}
}
let node0 = new Node(0)
let node1 = new Node(1)
let node2 = new Node(2)
let node3 = new Node('hello')
let node4 = new Node(4)
let node5 = new Node(5)
node0.insertChild(node1)
node0.insertChild(node2)
node1.insertChild(node3)
node1.insertChild(node4)
node2.insertChild(node5)
function dfsSearch(root, value){
let list = []
let target
let firstUncheckChild
list.push(root)
while(list.length){
target = list.shift()
target.checked = true
console.log(target.data)
if(target.data === value) return value
// 获取自己的第一个未被检查过的孩子
firstUncheckedChild = target.children.filter(v=>!v.checked)[0]
if(firstUncheckedChild){
list.push(firstUncheckedChild)
}else {
list.push(target.parent)
}
}
}
