Alice has two sorted arrays $\mathrm{A}[1, \ldots, \mathrm{n}], \mathrm{B}[1, \ldots, \mathrm{n}+1]$. She knows that A is composed of distinct positive numbers, and B is derived from inserting a zero into $A$. She would like to know the index of this zero. She wonders if you can design and analyse a fast algorithm for her to find the index of the zero in $B$.
She has provided the following example to ensure that the problem statement is clear.
A: $[ 1,3,4,6,7,8,9,20]$
B: $[1,3,0,4,6,7,8,9,20]$.
Your algorithm should return 2 in this case, which is the index of the zero in B.
What is the tightest upper bound of the best algorithm to do this task in terms of $n$ ?
(Here O represents big-oh)
- $O(n)$
- $O(logn)$
- $O(1)$
- $O(loglogn)$
