Skip to content

Commit bd64926

Browse files
taokexiataokexia
committed
add binarySearchAdv
1 parent 0d48fe9 commit bd64926

4 files changed

Lines changed: 93 additions & 2 deletions

File tree

‎JavaScript/Typical/Test.js‎

Lines changed: 17 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,4 +2,20 @@
22
var bs = require('./binarySearch');
33
var arr1 = [0, 1, 2, 3, 4, 5, 10, 23, 44, 66, 88, 99];
44
console.log(bs.binarySearch1(arr1, 10));
5-
console.log(bs.binarySearch2(arr1, 88));
5+
console.log(bs.binarySearch2(arr1, 88));
6+
7+
// 测试优化后的二分查找法
8+
console.log("=================测试优化后二分查找========================");
9+
var bsAdv = require('./binarySearchAdv');
10+
var arr2 = [1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 6, 6, 6, 6, 6, 6, 6, 6];
11+
console.log(bsAdv.floor(arr2, 4));
12+
console.log(bsAdv.ceil(arr2, 6));
13+
console.log(bsAdv.floor(arr2, 5));
14+
console.log(bsAdv.ceil(arr2, 5));
15+
// 比较性能
16+
console.time("binarySearch");
17+
console.log(bs.binarySearch1(arr2, 4));
18+
console.timeEnd("binarySearch");
19+
console.time("binarySearchAdv");
20+
console.log(bsAdv.floor(arr2, 4));
21+
console.timeEnd("binarySearchAdv");

‎JavaScript/Typical/binarySearch.js‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -37,4 +37,5 @@ function __binarySearch2(arr, l, r, target) {
3737
} else {
3838
return __binarySearch2(arr, l, mid-1, target);
3939
}
40-
}
40+
}
41+

‎JavaScript/Typical/binarySearchAdv.js‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/*
2+
* 优化二分查找
3+
* 之前实现的二分查找，如果查找的数组中存在大量的重复元素,会有重复运行的现象
4+
* 优化后：
5+
* 如果找到target，返回第一个target相应的索引index
6+
* 如果没找到target，返回比target小的最大值相应索引，如果这个最大值有多个，返回最大索引
7+
* 如果这个target比整个数组的最小元素值还小，则不存在这个target的floor值，返回-1
8+
*/
9+
module.exports.floor = function floor(arr, target) {
10+
let l = -1;
11+
let r = arr.length-1;
12+
while(l < r){
13+
// 向上取整避免死循环
14+
let mid = l + Math.ceil((r-l)/2);
15+
if(arr[mid] >= target) {
16+
r = mid-1;
17+
} else {
18+
l = mid;
19+
}
20+
}
21+
// 如果该索引+1就是target本身，该索引+1即为返回值
22+
if(l+1 < arr.length && arr[l+1] === target) {
23+
return l+1;
24+
}
25+
// 否则，该索引即为返回值
26+
return l;
27+
}
28+
/*
29+
* 优化二分查找
30+
* 之前实现的二分查找，如果查找的数组中存在大量的重复元素,会有重复运行的现象
31+
* 优化后：
32+
* 如果找到target，返回最后一个target相应的索引index
33+
* 如果没找到target，返回比target大的最小值相应索引，如果这个最小值有多个，返回最小索引
34+
* 如果这个target比整个数组的最大元素值还大，则不存在这个target的ceil值，返回1
35+
*/
36+
module.exports.ceil = function ceil(arr, target) {
37+
let l = 0;
38+
let r = arr.length-1;
39+
while(l < r) {
40+
// 向下取整避免死循环
41+
let mid = l+Math.floor((r-l)/2);
42+
if(arr[mid] <= target) {
43+
l = mid+1;
44+
} else {
45+
r = mid;
46+
}
47+
}
48+
// 如果该索引+1就是target本身，该索引+1即为返回值
49+
if(l+1 < arr.length && arr[l+1] === target) {
50+
return l+1;
51+
}
52+
// 否则，该索引即为返回值
53+
return l;
54+
}

‎README.md‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,21 @@
22

33
使用JavaScript来实现从常用的算法和数据结构
44

5+
JavaScript用于测试算法性能的常用方法总结:<br/>
6+
方法一：
7+
8+
console.time("time");
9+
// 测试的算法
10+
console.timeEnd("time");
11+
12+
方法二：
13+
14+
var start = Date.now();
15+
// 测试的算法
16+
var end = Date.now();
17+
console.log(end-start);
18+
19+
520
排序算法：
621

722
- [冒泡排序](https://github.com/taokexia/JavaScript-Algorithm/blob/master/JavaScript/Sort/BubbleSort.js)
@@ -20,3 +35,8 @@
2035
- [最大堆](https://github.com/taokexia/JavaScript-Algorithm/blob/master/JavaScript/Heap/MaxHeap.js)
2136
- [最大索引堆](https://github.com/taokexia/JavaScript-Algorithm/blob/master/JavaScript/Heap/IndexMaxHeap.js)
2237
- [最小堆](https://github.com/taokexia/JavaScript-Algorithm/blob/master/JavaScript/Heap/MinHeap.js)
38+
39+
经典算法：
40+
41+
- [二分查找](./JavaScript/Typical/binarySearch.js)
42+
- [二分查找优化](./JavaScript/Typical/binarySearchAdv.js)

0 commit comments

Comments
 (0)