Given an array of a million sorted values, how many comparisons would a linear search and a binary search each need?
Up to a million for the linear search, and twenty for the binary search.
import math
for n in (1000, 1000000):
linear = n
binary = math.ceil(math.log2(n + 1))
print(f"n = {n:>8} linear = {linear:>8} binary = {binary:>3}")
n = 1000 linear = 1000 binary = 10
n = 1000000 linear = 1000000 binary = 20
So why is the binary search so much smaller? Because each comparison throws away half of what is left. A list of a million items has a bit depth of about twenty, so after twenty rounds there is nothing left to look at.
And the number twenty is worth remembering, because it barely moves. A million and a thousand items differ by a thousand times, and the binary search only goes from ten comparisons to twenty.
So the answer to the question in one line is this. A million for the linear search and twenty for the binary search, and the difference is a factor of fifty thousand.
The last question in this topic asks about the harder kind of question.