Give an on algorithm to determine if there exists an integer

Give an o(n) algorithm to determine if there exists an integer i such that -4[i] = i in an array A[1..n] of integers where A[1]

Solution

1. We can use the idea as how the Binary search works, this problem can be thought as to find an index i such that A[i] = i .So there will be no input as Key

1. Find low and high using array. Find the mid.
2. Check if mid is more than the array value then search in left. by making as high = mid -1
3. Check if mid is less than the array value then search in right by making low as mid+1;
4. Other wise return mid;

If No such index found return -1;


Algorithm Search(A)
Start
low = 1 , high = length(A)
   while low < high
   mid = (low + high)/ 2
if A[mid] < mid //index is more so we have to search in left part as elements are even higher in right
   high =. mid - 1 ;
else if A[mid] > mid //index is less so we have to search in right part as elements are even lower in left
   low =. mid + 1 ;
   else
   return mid;
return -1

end

     

Time Complexity is O(log n)


ii). If we need a loose bound algorithm: O(N)

Start from the index 0 till the length of array check if index i equal to array element. If Yes return the elment
otherwise return -1

Algorithm Search(A)
Start
  for i in 1: length(A)
   if A[i] == i
   retun i

return -1;
End