大家好，前几章我们讲了冒泡，选择，插入，归并和快速排序，了解了一些比较熟知的排序算法，今天呢我们要聊的就是顺序和二分搜索，是两种搜索算法，理解后对我们的实际工作还是很有用处的，接下来让我们来看看这两种搜索算法吧！

顺序搜索

这种算法非常低效，但是非常适合入门，

顺序搜索的思路

• 遍历数组。

• 找到跟目标相等的元素，就返回它的下标。

• 遍历结束后，如果没有搜索到目标值，就返回 -1。

实现

Array.prototype.sequentialSearch = function (item) {
    for (let i = 0; i < this.length; i++) {
        if (this[i] === item) {
            return i
        }
    }
    return -1
}

const res = [1, 2, 3, 4, 5]
console.log(res.sequentialSearch(3));
console.log(res.sequentialSearch(6));
// 2 -1

顺序搜索的时间复杂度

• 遍历数组是一个循环操作。

• 时间复杂度：O(n)。

二分搜索

二分搜索又称折半搜索，是一种在 中查找某个特定元素的算法，它比顺序搜索的效率要高的多，因为每次搜索都会减半，而不用像顺序搜索一样把每个元素都遍历一遍。

二分搜索的思路

• 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。

• 如果目标值大于或者小于中间的元素，则在大于或小于中间元素的那一半数组中搜索。

• 如果搜索到最后还没找到目标值，就返回 -1。

实现

Array.prototype.binarySearch = function (item) {
    let low = 0
    let high = this.length - 1
    while (low <= high) {
        const mid = Math.floor((low + high) / 2)
        const element = this[mid]
        if (element < item) {
            low = mid + 1
        } else if(element > item) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

const res = [1, 2, 3, 4, 5]
console.log(res.binarySearch(3));
console.log(res.binarySearch(6));
// 2 -1 

二分搜索的时间复杂度

• 每一次比较都使搜索范围缩小一半。

• 时间复杂度：O(logN)。

End~~