-
Notifications
You must be signed in to change notification settings - Fork 4
/
BinSearch.js
182 lines (132 loc) · 4.66 KB
/
BinSearch.js
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
/**
* @Author: zhuxiankang
* @Date: 2018-10-30 09:13:24
* @Desc: 二分查找
*/
/**
*
二分查找:
如果你要查找的数据是有序的,二分查找算法比顺序查找算法更高效。
1、将数组的第一个位置设置为下边界(0)。
2、将数组最后一个元素所在的位置设置为上边界(数组的长度减1)。
3、若下边界等于或小于上边界,则做如下操作:
a. 将中点设置为数组长度除以2。
b. 如果中点的元素小于查询的值,则将下边界设置为中点元素所在下标加1。
c. 如果中点的元素大于查询的值,则将上边界设置为中点元素所在下标减1。
d. 否则中点元素即为要查找的数据,可以进行返回。
*/
/**
* @Author: zhuxiankang
* @Date: 2018-10-31 08:37:11
* @Desc: 二分法查找数据
* @Parm:
*/
function binSearch(arr, data) {
let upperBound = arr.length - 1
let lowerBound = 0
while(lowerBound <= upperBound) {
let mid = Math.floor((upperBound + lowerBound) / 2)
if(arr[mid] < data) {
lowerBound = mid + 1
} else if(arr[mid] > data) {
upperBound = mid - 1
} else {
return mid
}
}
return -1
}
/**
* @Author: zhuxiankang
* @Date: 2018-10-31 08:37:34
* @Desc: 插入排序
* @Parm:
*/
function insertionSort(arr) {
var temp, inner
for (var outer = 1; outer <= arr.length - 1; ++outer) {
// 待插入的数据
temp = arr[outer]
inner = outer
//
// 找到需要插入的位置,其他数据往后移动,并为该位置提供空间
while (inner > 0 && (arr[inner - 1] >= temp)) {
arr[inner] = arr[inner - 1]
--inner
}
// 将待插入数据插入适应位置
arr[inner] = temp
}
}
let arr = [65,1,6,3,8,2,9,1,11,22,33,7,89,65,37,215,13,8,897,23,55,55,55,78,899,212,45]
insertionSort(arr)
console.log(arr)
console.log(binSearch(arr, 1))
/**
*
计算重复数据:
当binSearch() 函数找到某个值时,如果在数据集中还有其他相同的值出现,那么该函数会定位在类似值的附近。
换句话说,其他相同的值可能会出现已找到值的左边或右边。
所以一个统计重复值的函数要怎么做才能确保统计到了数据集中出现的所有重复的值呢?
最简单的解决方案是写两个循环,两个都同时对数据集向下遍历,或者向左遍历,统计重复次数;然后,向上或向右遍历,统计重复次数。
*/
function binRepeatCount(arr, data) {
let count = 0
let position = binSearch(arr, data)
if(position > -1) {
++ count
let i = position
while(arr[++ position] === data) {
++ count
}
while(arr[-- i] === data) {
++ count
}
}
return count
}
console.log(binRepeatCount(arr, 65))
/**
*
查找文本数据:
*/
let strArr = `The nationalism of Hamilton was undemocratic. The democracy of Jefferson was
in the beginning, provincial. The historic mission of uniting nationalism and
democracy was in the course of time given to new leaders from a region beyond
the mountains, peopled by men and women from all sections and free from those
state traditions which ran back to the early days of colonization. The voice
of the democratic nationalism nourished in the West was heard when Clay of
Kentucky advocated his American system of protection for industries; when
Jackson of Tennessee condemned nullification in a ringing proclamation that
has taken its place among the great American state papers; and when Lincoln
of Illinois, in a fateful hour, called upon a bewildered people to meet the
supreme test whether this was a nation destined to survive or to perish. And
it will be remembered that Lincoln's party chose for its banner that earlier
device--Republican--which Jefferson had made a sign of power. The "rail splitter"
from Illinois united the nationalism of Hamilton with the democracy of Jefferson,
and his appeal was clothed in the simple language of the people, not in the
sonorous rhetoric which Webster learned in the schools.`.split(' ')
// 注意这个数组里没有区分标点符号
console.log(strArr)
/**
* @Author: zhuxiankang
* @Date: 2018-10-30 08:54:57
* @Desc: 线性查找数组的索引
* @Parm:
*/
function findIndex(arr, data) {
for(let i=0; i<arr.length; i++) {
if(arr[i] === data) {
return i
}
}
return -1
}
console.time('线性查找耗时')
console.log(findIndex(strArr, 'rhetoric'))
console.timeEnd('线性查找耗时')
insertionSort(strArr)
console.log(strArr)
console.time('二分查找耗时')
console.log(binSearch(strArr, 'rhetoric'))
console.timeEnd('二分查找耗时')