Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $𝑂(\log n)$.
This is a nice open-ended question to test how well students understand the referred concepts. Here is how I could show my understanding about the conventional binary search.
First, the algorithm time is always $O(\log n)$ in its usually implementation, i.e, an (indexed) sorted array (SA) or a binary search tree (BST) in the RAM model + comparison model (the computation model that is usually used when we talk about binary search). Even if the algorithm happens to find the wanted element in the very first iteration, i.e., comparing the wanted element against the element in the middle of the SA or the root of the BST, it takes $O(\log n)$ time still. Even in the worst time, it takes $O(\log n)$ time still.
Second, the algorithm time will be $O(1)$ when its runs on some particular subsets of the searching problems in some particular ways as illustrated below.
The number of elements, i.e., the length of the array or the number of elements in BST is bounded by a constant. In this case, even a linear search algorithm will run in $O(1)$ time. Note that the wanted element may or may not be in the given elements.
Note this situation is different from the situation when the number of different values of the element (as used in the comparison) is bounded. We may need $\Theta(\log n)$ steps to find the index of a $2$ in an sorted sequence of $n$ numbers all of which are 1, 2, or 3.
- The wanted element is in the middle of the SA, or in the one-quarter or three-quarter position of the SA, and so on but within a bounded times of iterations. The exact indices of these positions depend on the exact implementation of the binary search. An implementation might check the element at index $(n-1)/2$ first in an array with indices $0,1,\cdots, n$ and odd $n$ or check the element at index $(n+1)/2$ first. The former implementation might need $\Theta(\log n)$ to find the element at index $(n+1)/2$.
- The wanted element is within a bounded depth away from the root of the BST.
- We could construct various special set of searching situations where the time for a particular implementation of the algorithm will be $O(1)$ by reverse engineering. Specifying a constant $c$. Searching an array by binary search algorithm. If it ends with $c$ steps, we include that problem instance. All together we will find a set of problem instances where the binary search algorithm will run within $c=O(1)$ steps.
Here is a shorter version that could be used as a reference answer to the question for grading. Again, only the conventional binary search algorithms are considered.
The binary search algorithm always runs in $O(\log n)$ time in the usual computation model.
If the wanted element is among the elements that could be possibly compared within $c$ comparisons for some constant $c$, then the algorithm time is $O(1)$. It happens when the number of total elements is bounded by a constant, when the wanted element is the element in the middle of a sorted array of odd length and when the depth of the wanted element is less than a constant where a binary search tree is used.