Given an array Aln of n integers such that for all j 1 lesst

Given an array A[l..n] of n integers, such that for all j, 1 lessthanorequalto j

Solution

We have 2 search algorithms

1.Linear Search (unsorted array)

2.Binary Search (sorted array)

Among these 2 Binary Search is the efficent search.

In your question A[j] - A[j+1] <=1 for all j, 1 <= j < n So array should be ascending order or descending order.

But if A[j]=z for a given value z, x <= z <= y, where A[1]=x and A[n]=y. Array should be in ascending order.

Algorithm to find an index for given value is

index IndexSearch(arraylist, item):
first = 0
last = len(arraylist)-1
while first<=last and not found:
j = (first + last)/2
   if alist[j] == item:

return j;

   else:
   if item < alist[j]:
   last = j-1
   else:
   first = j+1
return