Binary search is *not* O(log(n)) in this problem

  • 0

    Binary search is used to find elements in O(log(n)) in sorted arrays. However, the algorithm is looking for a unique element and that is independent from the fact that the array is sorted. Namely, the unique element can be anywhere in the array, independently of its index.

    I am looking for a proof that binary search is better than linear array lookup in this particular example, but I can't think of any. If you have any information, and prove me wrong, I am all ears! :-)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.