Jump ahead √n elements at a time, looking only at the last value of each block, until a block ends at or above the target. Then scan that one block from its start.
- Average time
- O(√n)
- Space
- O(1)
Jump ahead √n elements at a time, looking only at the last value of each block, until a block ends at or above the target. Then scan that one block from its start.