Hello,

I would like to ask about the complexity of a parallel binary search of an element in an array of N elements.

I'm reading an article, they explain that a thread finds the searched element through one memory access in the best case or through 2log N memory accesses in the worst case

They say that each thread performs two memory accesses : to check the lower bound and the upper bound to correctly update the index for the next iteration. I don't understand why the two bounds need to be checked. Can someone explain it to me ?

Thank you.