Things on this page are fragmentary and immature notes/thoughts of the author. Please read with your own judgement!
In [22]:
from pathlib import Path
In [9]:
x = [i * 10 for i in range(1, 16)]
x
Out[9]:
In [10]:
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 b
Find the least element in the array greater than or equal to target.
In [ ]:
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]
}
In [11]:
eytzinger(x)
Out[11]:
In [12]:
eytzinger(sorted(x, reverse=True))
Out[12]:
Find the max element in the array smaller than or equal to target.
In [ ]:
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]
}
References¶
In [ ]: