News for hackers. Stuff that matters.

A comment on Beautiful branchless binary search. Parent comment

Re:Beautiful branchless binary search by zelphirkalt on Friday April 28, 2023 @03:35AM (#35738561)
Isn't that like storing a heap inside an array, with indices and values like this:

    0: top of heap,
    1: left of top,
    2: right of top,
    3: left of left of top
    ...

?
[ Parent | on HN ]
Re:Beautiful branchless binary search by contravariant on Friday April 28, 2023 @05:39AM (#35739255)
It is, but so is storing a sorted array.
[ Parent | on HN ]
Re:Beautiful branchless binary search by account42 on Friday April 28, 2023 @06:28AM (#35739531)
It's still misleading to call this a binary search when that is commonly understood as an algorithm operating on a sorted range which is not just an arbitrary datastructure but something that already exists in many situations. If you just need fast lower_bound lookup for a set that you control and which has no other uses then sure this is nice, but more commonly you only care if an element is in the set and in that case if you can control the data structure then there are many more options.
[ Parent | on HN ]
Re:Beautiful branchless binary search by eska on Friday April 28, 2023 @07:19AM (#35739888)
I agree with you.

Algorithms don’t exist in a bubble, but are always accompanied with a data structure.

A heap sorted array is different from a linearly sorted array. Binary search is only defined for the latter.

[ Parent | on HN ]