answer in psuedo code Given a sorted array A of n numbers an

answer in psuedo code

Given a sorted array A of n numbers and an additional number x, give an algorithm that checks if there is i so that (A[i])2 = x

Solution

Basically we need to find out if A(i)*A(i)=x for any i from 1 to n.

Basically if square root x exists in array A. Let square root of x be sqx, we should also search for -sqx.

As A is already so we can do a binary search.

func search(A,st,end,x)
{
   if(end<st)
   {
       return -1;
   }
   mid = st+(end-st)/2;
   if(A[mid]==x)
   {
       return mid;
   }
   else if (A[mid]>x)
   {
       search(A,st,mid-1,x)
   }
   else
   {
       search(A,mid+1,end,x)
   }
}

We need to run search(A,1,n,sqx) and search(A,1,n,-sqx) if any of them return a value other than -1 then we have found the answer.