$($a$)$ Given a sorted array A of n numbers, a target number t and integer k$,$ design and analyze an efficient algorithm which finds k closest $($the distance between two real numbers x and y is defined to be dist$($x$,$ y$)=|$x $$ y$|)$ elements to t in A$.$ explain the algorithm as well.

$($b$)$ Many data processing problems in $1-$D become much harder when the data points are from spaces of higher dimensions. One key reason is that sorting usually does not help or even make sense at all for points in higher dimensions. Consider the same question as part $($a$)$ in $3-$dimension: we are given n points $\{($x$1,$ y$1,$ z$1),...,($xn$,$ yn$,$ zn$)\}$ stored in an array A$,$ a target point t $=($tx$,$ ty$,$ tz $)$

and integer k$,$ design and analyze an efficient algorithm which finds k closest elements to t in A$.$ Here the distance between two points pi $=($xi$,$ yi$,$ zi$)$ and pj $=($xj $,$ yj $,$ zj $)$ is defined to be dist$($pi$,$ pj $)=$ p$($x$1$ y$1)^2+($x$2$ y$2)^2+($x$3$ y$3)^2.($Note that points in $3-$dimension can not be sorted in general; even we are promised that the x$-$coordinate x$1,$ x$2,...,$ xn of these n points

are sorted in A does not seem to help solving the problem in any conceivable way$)$