While mathematically finding the complexity of the binary search algorithm, We actually assume that there are 2K elements in the list. During the process we come to this particular part and the statement in my book:
"Hence, at most 2K + 2 = 2logn + 2 comparisons are required to perform a binary search when the list being searched has 2K elements. (If n is not a power of 2, the original list is expanded to a list with 2K+1 terms, where k = ⌊logn⌋, and the search requires at most 2 $\lceil logn\rceil $ + 2 comparisons.) Consequently, a binary search requires at most ϴ(logn) comparisons. "
There is one thing I do not understand in this:
1)How is this algorithm a ϴ(logn)? From what I understand a big ϴ is only when it is both big O and big Ω, but where are the functions, f(x) and g(x) such that f(x) is both O(g(x)) as well as Ω(g(x))?
To get a $\Theta$ result for the worst case complexity, you basically want to furnish the worst case (which gives an $\Omega$ result, i.e. a lower bound on the worst case runtime) and prove it is the worst case (which gives an $O$ result, i.e. an upper bound on the worst case runtime). It may be easier to proceed in the other order: determine from the structure of the algorithm what the worst possible case could ever be, and then construct an input that leads to this behavior.
For binary search on $2^K$ elements, the worst case situation would be $K$ halvings of the array, because at that point there is only one element left (so you merely check whether it is the element you want and then you're done). That gives an $O$ result. To get an $\Omega$ result you can furnish an array of size $2^K$ and an element to search for so that binary search actually takes $K$ halvings, or perhaps just a little bit less. Hint: put the desired element in the second position and nowhere else.