Things on this page are fragmentary and immature notes/thoughts of the author. Please read with your own judgement!
from pathlib import Pathx = [i * 10 for i in range(1, 16)]
x[10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150]def eytzinger(a):
n = len(a)
b = [0] * (n + 1)
def _eytzinger(i=0, k=1):
if k <= n:
i = _eytzinger(i, 2*k)
b[k] = a[i]
i = _eytzinger(i+1, 2*k+1)
return i
_eytzinger()
return bFind the least element in the array greater than or equal to target.
pub fn binary_search_branchless(data: &[u64], target: u32) -> u64 {
let mut idx = 1;
while idx < data.len() {
let el = data[idx];
idx = 2 * idx + usize::from(el < target);
}
idx >>= idx.trailing_ones() + 1;
data[idx]
}eytzinger(x)[0, 80, 40, 120, 20, 60, 100, 140, 10, 30, 50, 70, 90, 110, 130, 150]eytzinger(sorted(x, reverse=True))[0, 80, 120, 40, 140, 100, 60, 20, 150, 130, 110, 90, 70, 50, 30, 10]Find the max element in the array smaller than or equal to target.
pub fn binary_search_branchless_2(data: &[u64], target: u64) -> u64 {
let mut idx = 1;
while idx < data.len() {
let el = data[idx];
idx = idx * 2 + usize::from(el > target);
}
idx >>= idx.trailing_ones() + 1;
data[idx]
}