Counting Search Steps

Each comparison halves the range that could still contain the target: $n$, then $n/2$, then $n/4$, and so on, so after $x$ comparisons the range has size $n/2^x$. The search stops once the range is empty, which happens right after it reaches size $1$, so solve $n/2^x=1$, giving $2^x=n$ and $x={\log }_{2}n$. The worst case is about ${\log }_{2}n$ comparisons, against about $n$ for a linear search.

${\log }_{2}4,096=12$, so about 12 comparisons. Doubling the array to $8,192$ adds exactly one more halving, so it needs ${\log }_{2}8,192=13$. That is one more, regardless of how large the array already was.

${\log }_{2}500,000$ is under 20, while linear search’s worst case is about 500,000 comparisons, so the two are already several orders of magnitude apart. Linear search’s cost scales proportionally with $n$, so doubling $n$ doubles the work. Binary search’s cost scales with how many times you can halve $n$, so doubling $n$ only adds one more comparison. The gap between the two widens as $n$ grows.