-
Notifications
You must be signed in to change notification settings - Fork 11
/
Copy pathindex.ts
31 lines (26 loc) · 905 Bytes
/
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
export function ternarySearch(
haystack: number[],
needle: number,
left: number = 0,
right: number = haystack.length - 1
): number | undefined {
if (right >= left) {
// Thirds, so we have two middles
let leftMiddle = Math.round(left + Math.abs(left - right) / 3);
let rightMiddle = Math.round(right - Math.abs(left - right) / 3);
if (haystack[leftMiddle] === needle) {
return leftMiddle;
} else if (haystack[rightMiddle] === needle) {
return rightMiddle;
}
if (needle < haystack[leftMiddle]) {
return ternarySearch(haystack, needle, left, leftMiddle - 1);
} else if (needle > haystack[rightMiddle]) {
return ternarySearch(haystack, needle, rightMiddle + 1, right);
}
return ternarySearch(haystack, needle, leftMiddle + 1, rightMiddle - 1);
}
}
const array = [...Array(90).keys()];
// 3
console.log(ternarySearch(array, 3));