Search Insert - Walkthrough (Tracing execution)

Let's trace $nums = [1, 3, 5, 6]$ and $target = 2$. Initially, $left = 0$ and $right = 3$.

Step 1: $mid = 1$, $nums[1] = 3 > 2$, so $right = 0$. Step 2: $mid = 0$, $nums[0] = 1 < 2$, so $left = 1$. Now $left > right$, so the loop exits and returns $left = 1$.

The answer is $1$, which is correct: insert $2$ at index $1$ to keep the array sorted. You made $2$ comparisons, which is $O(\log 4) = 2$.