-
Notifications
You must be signed in to change notification settings - Fork 2
/
index.ts
41 lines (36 loc) · 1.14 KB
/
index.ts
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
import {findAllNearby} from '../../../helpers';
import {equalThan} from '../../../helpers/comparator';
import algorithm, {Algorithm, AlgorithmProps, Options} from '../Algorithm';
const jumpSearch = (options?: Options<number>): Algorithm<number> => {
const algoOptions = {
compareFunction: equalThan,
...options,
};
const search = (values: number[], seek: number): number[] => {
if (!values) return [];
const len = values.length;
const step = Math.floor(Math.sqrt(len));
let current = step - 1;
// finding the block where element is present
while (current < len && values[current] < seek) {
current += step;
}
// find seeked element inside block using linear search
for (let i = current - step + 1; i <= current && i < len; i++) {
if (seek == values[i]) {
return findAllNearby(values, seek, i, algoOptions.compareFunction);
}
}
return [];
};
const algoProps: AlgorithmProps<number> = {
run: (values, seek) => {
const result = search(values, seek);
return {
result,
};
},
};
return algorithm(algoProps);
};
export default jumpSearch;