viviier

算法 - 二分查找 斐波那契

二分查找

对有序的数据进行二分查找比顺序查找更高效。

例子

简单例子

我们有1-100个数据:
1 25 50 75 82 100
想要在其中找到数字82,进行二分查找
51 75 82 100
第一次mid”索引”为(0 + 100) / 2 = 50(Math.floor),返回太小,因此下限变为mid + 1 = 51,上限不变
75 82 88 100
第二次mid”索引”为(51 + 100) / 2 = 75(Math.floor),返回太小,因此下限变为mid + 1 = 76,上限不变
76 82 88 100
第三次mid”索引”为(76 + 100) / 2 = 88(Math.floor),返回太大,因此下限不变,上限变为mid - 1 = 87
76 81 82 87
第四次mid”索引”为(76 + 87) / 2 = 81(Math.floor),返回太小,因此下限变为mid + 1 = 82,上限不变
82 84 87
第五次mid”索引”为(82 + 87) / 2 = 84(Math.floor),返回太大,因此下限不变,上限变为mid - 1 = 83
82 83
第六次mid”索引”为(82 + 83) / 2 = 82(Math.floor),返回mid”索引”

二分查找的简单描述:
将数组的第一个位置设置为下边界(0)
将数组的最后一个元素所在的位置设置为上边界(arr.length - 1)
当下边界小于等于上边,进入while循环:
a. 将mid设置为(下边界 + 上边界)/ 2
b. 如果arr[mid]的元素小于查询的值,则下边界变为mid + 1
c. 如果arr[mid]的元素大于查询的值,则上边界变为mid - 1
d. 否则mid等于查询的值,返回mid
如果没有找到,退出循环,返回-1

实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
* @二分查找
* @arr, data 传入参数
* @lowerBound, upperBound, mid 定义数组左边取值范围,定义数组右边取值范围,相加为总范围,mid为总范围除2取中间值
* @循环判断中间值arr[i]小于 大于 等于data,做出相应的返回
*/
function binSearch(arr, data) {
let lowerBound = 0
let upperBound = arr.length - 1
while(lowerBound <= upperBound) {
let mid = Math.floor((lowerBound + upperBound) / 2)
if(arr[mid] < data) {
lowerBound = mid + 1
} else if(arr[mid] > data) {
upperBound = mid - 1
} else {
return mid
}
}
return -1
}

我们来测试一下:

1
2
let arr = [1,2,3,4,5,6,7,8,9,10,11,12,13,45,55]
console.log(binSearch(arr,5)) // 4

计算重复次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
* @arr, data
* @count, position 计数器以及是否找到元素
* @如果找到了,计数器加1,然后双重循环遍历,一个向上position + 1,一个向下position - 1,找相同元素
*/
function count(arr, data) {
let count = 0
let position = binSearch(arr, data)
if(position > -1) {
++count
for(let i = position - 1; i > 0; --i) {
if(arr[i] == data) {
++count
}else {
break;
}
}
for(let i = position + 1; i < arr.length; ++i) {
if(arr[i] == data) {
++count
} else {
break
}
}
}
return count
}

我们来测试一下:

1
2
let arr = [1,1,1,1,1,2,3,3,4,5,6,7,8,9,9,9,10,11,12]
console.log(count(arr, 9)) // 3

斐波那契

实现

1
2
3
4
5
6
7
8
9
10
11
12
/*
* @递归
* @a1 = 1, a2 = 2, a(n) = a(n-1) + a(n-2) **n>=3, n∈N* 通项公式
*/
function recurFib(n) {
if(n < 2) {
return n
} else {
return recurFib(n-1) + recurFib(n-2)
}
}

我们来测试一下:

1
console.log(recurFib(10)) // 55

优化

动态规划解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* @太多的值在递归调用中被重新计算,所以效率低下
* @用数组记载已经被纪录的值,优化效率
*/
function dycFib(n) {
let val = []
for(let i = 0; i<= n; i++) {
val[i] = 0
}
if( n == 1 || n == 2) {
return 1
} else {
val[1] = 1
val[2] = 2
for(let i = 3; i <= n; i++) {
val[i] = val[i-1] + val[i-2]
}
return val[n-1] // 0 - 10 是11个数
}
}

我们来测试一下:

1
console.log(dycFib(10)) // 55

迭代解决
1
2
3
4
5
6
7
8
9
10
11
function iterFib(n) {
let last = 1
let nextLast = 1
let result = 1
for(let i = 2; i < n; i++) {
result = last + nextLast
last = nextLast
nextLast = result
}
return result
}

我们来测试一下:

1
console.log(iterFib(10)) // 55

------本文结束感谢阅读------