Binary Search
Modified 2023-06-25
Typescript
The idea is to cut 50% of the sorted dataset in half.
export default function bs_list(haystack: number[], needle: number): boolean {
let lo = 0;
let hi = haystack.length
do {
const m = Math.floor(hi - (hi - lo) / 2)
const v = haystack[m]
if (v === needle) {
return true
} else if (v > needle) {
hi = m
} else {
lo = m + 1
}
} while (lo < hi)
return false
}Special Case
The extra check in the second for loop is to prevent going out of bounds due to some error. Also note that even though we use two for loops, the complexity is only on Osqr(N).
export default function two_crystal_balls(breaks: boolean[]): number {
const jmpAmount = Math.floor(Math.sqrt(breaks.length))
let i = jmpAmount
for (; i < breaks.length; i += jmpAmount) {
if (breaks[i]) {
break;
}
}
i -= jmpAmount;
for (let j = 0; j < jmpAmount && i < breaks.length; ++j, ++i) {
if (breaks[i]) return i
}
return -1
}