My thoughts on You can beat binary search: You can beat binary search
Commentary
- You can beat binary search: Quad Search
- This is creative. Instead of just halving the list, we do a buckets of 16, quads, and compute which of the buckets the element can be. Since we have the max of each bucket. We can find the bucket and parallelly then compare each element in it.
- Surprisingly, this is better for large arrays, and with multiple cores this will outperform binary search easily. Because we are not diving the array into halves anymore, we are picking the most possible region where the element could be and parallel searching it in those.