1

Binary search of a sorted array may have poor cache locality, due to random access of memory, but linear search is slow for a large array. Is it possible to design a hybrid algorithm? For example, you could divide a sorted array of length 100 into 10 chunks, each of length 10. Within each chunk, I do a simple linear search, but on a "global" level, I do a binary search in the conventional sense: if the searched value is not in either the 1st chunk or the 10th chunk, I will look into the middle, i.e. the 5th chunk (because 5 = floor((1+10)/2). If the 5th chunk doesn't contain the searched value, I will look at the 3rd chunk or the 7th chunk, depending on if the searched value is smaller than or greater than the numbers in the 5th chunk.

Have people considered this kinds of algorithms? Is is worth the implementation effort?

felix
  • 647
  • 1
  • 6
  • 10
  • 1
    not an expert in the matter but any such approach would most likely have very big overhead that would diminish any advantage of less cache misses ... not to mention additional branching so my bet is that binary search would be far more faster anyway... – Spektre Oct 14 '20 at 09:43
  • 1
    By the time you get a "fast enough" linear search you'd have to split in chunks so small that the overhead would be very high. Think about 1 billion items to search for. If you split them in chunks of 1000 items, you end up with 1.000.000.000 / 1000 = one million of chunks. Worst case scenario you end up doing 1.000.000 / 1000 = 1000 linear searches. But with full binary search you'd have a worst case of 30 steps (I think I counted correctly, not 100% sure). – ChatterOne Oct 14 '20 at 10:10
  • This consideration would start to make sense when the list of values is not just read-only, and must be represented as a search tree. In that case your idea can be found in B-trees. – trincot Oct 14 '20 at 10:15

0 Answers0