Question

Consider the task of searching a sorted array $\mathbf{A}\left[1,\dots ,n\right]$ for a given element $\mathbf{x}\mathbf{:}$ a task we usually perform by binary search in time $\mathbf{O}\left(\mathrm{logn}\right)$ . Show that any algorithm that accesses the array only via comparisons (that is, by asking questions of the form “is $\mathbf{A}\left[i\right]\mathbf{\le }\mathbf{z}$ 0?”), must take $\mathbf{\Omega }\left(\mathrm{logn}\right)$ steps.

Short answer

Yes, any algorithm that accesses the array only via comparisons take $\Omega \left(\log n\right)$ steps.

Step-by-step solution

Explain Binary Search

Binary search is implemented on a sorted array. Binary search always starts with the mid element. Mid element compared with every other element and the element to be searched will be found.

Show that any algorithm that accesses the array via comparisons takes Ω(logn) steps.

Knowing that a query produces two kinds of results that is yes or no. The array$A\left[1,\dots ,n\right]$can be divided into two parts based on the result of the query.

In the best case, the two divided parts will be equal and the search can be scaled regardless of the query result.

Therefore, To locate a unique element by comparisons, it takes $\Omega \left(\log n\right)$ steps