Re:Binary Search: A new implementation that is up to 25% faster
by kazinator on Tuesday July 21, 2020 @09:53AM
(#23906775)
Binary search is used when you can't optimize the data structure. You have a sorted array, and have to work with that.
If you store the middle element together with its first two quartiles, you're making a B-tree. You will need indirection (pointers) to locate the other chunks that are not stored together and so it goes.
"Binary search" usually refers to the sorted array algorithm, though of course in the abstract sense of subdivision, any subdivision-by-two search is binary and in that sense we have the term "binary search tree".
If you store the middle element together with its first two quartiles, you're making a B-tree. You will need indirection (pointers) to locate the other chunks that are not stored together and so it goes.
"Binary search" usually refers to the sorted array algorithm, though of course in the abstract sense of subdivision, any subdivision-by-two search is binary and in that sense we have the term "binary search tree".