课程名称：JavaScript版数据结构与算法
课程章节：第11章 进阶算法之“搜索排序”
主讲老师：lewis
课程内容：
今天学习的内容包括：
11-7 JavaScript 实现：顺序搜索——通过for循环判断是否存在，性能比较差，一般不使用。
11-8 JavaScript 实现：二分搜索——折半进行搜索，一般使用较多。
课程收获：
顺序搜索
顺序搜索的思路
- 遍历数组。
- 找到跟目标值相等的元素，就返回它的下标。
- 遍历结束后，如果没有搜索到目标值，就返回-1。
for (let i = 0; i < this.length; i++) {
if(this[i] === item){
return i
}
}
return -1
顺序搜索的时间复杂度
- 遍历数组是一个循环操作。
- 时间复杂度：O(n)。
二分搜索
二分搜索的思路
- 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束。
- 如果目标值大于或则小鱼中间元素，则在大于或则小于中间元素的那一半数组中搜索。
- 如果没有搜索到则返回-1。
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
二分搜索的时间复杂度
- 每一次比较都使搜索范围缩小一半。
- 时间复杂度：O(logN)。
今天学习了 顺序搜索、二分搜索，二分搜索要比顺序搜索的时间复杂度要小，他的每次比较都使搜索范围缩小一半，故一般使用二分搜索，时间复杂度为O(logN)。对自己说一句，加油😀~
坚持打卡，坚持学习！明天见💪~