Problem $3$

We have a dictionary $D,$ which is an array of $n$ distinct strings, sorted in lexicographic order. We also have a procedure available to us$,$ Compare$-$Strings $(x,y),$ which will compare two strings $x$ and $y$ in $(1)$ time, and return $-1$ if $x$ comes before $y,0$ if they are identical, and $+1$ if $y$ comes before $x$ in lexicographic order.

Now for an input array $C$ that contains $n-1$ of the $n$ strings in $D$ and is not sorted, we would like to find the string that is missing in $C.$ For example, if $D=$ coffee, kombucha, slushy, soda, tea $>,$ and $C=$ kombucha, tea, soda, coffee, $>,$ we would like to return slushy.

Develop an efficient algorithm to solve this problem. Your algorithm should be in$-$place, i$.$e$.,$ it should use at most $(1)$ extra space. The na$$ve algorithm to beat works in $(nlogn)$ time as we could search for each string in $C$ using binary search on $D,$ which would take $(logn)$ time per string. Prove the correctness and analyze the runtime and space requirement of your algorithm.

Solutions I previously found did not factor in that C is unsorted, and D is sorted. Please factor that in :)