线性搜索

一种寻找某一特定的搜索算法

按一定的顺序检查数组中每一个元素，直到找到想要找的特定值为止。

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，
}

查找最大（小）值

1. 将数组的第0项作为最小值
2. 依次拿数组的剩余项和最小值作比较

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)
        }
        
    }
}