Lower bound for finding a value in sorted array

Question

Suppose we have a sorted array of unique elements, A[n]. I am trying to find the lower bound for finding a specific element x in the array. I suspect the lower bound to be log_2(n+1).

I tried to use a decision tree to solve this, and indeed we know between 2 elements which is greater, which gives 2 for the base of logarithm, but why all the possible cases n+1?

• Alexander: If you're looking for a lower bound, it's O(1). The element x could be the first element chosen, thus terminating your algorithm in constant time.

Answer 1

The algorithm you're thinking of is Binary Search.

It has a lower bound of O(1), which occurs in its best case: the first element picked is the desired element x. No further searching is required.

It has an upper bound of O(log_2(n)). Every time you pick an element and you decide if you need your next search to move higher or lower, you're eliminating half of the search space. Since each step halves the search space, the question becomes "how many times can I divide the size of the search space in 2, until I reach a single element"? This question of repeated halving is the opposite of repeated doubling (exponentiation), and is solved by a logarithm.