Consider the sorted array
45 47 49 50 55 57 66
Now I have chosen k = 1. That means the only place where we are going to get a hit is the highlighted position.
Now calculate 49-1 = 48 and 49+1 =50 (ie. 49+k and 49 - k is calculated)
Now if we can find these values in the array that means the algorithm returns true value and for that particular entry (in this case 49) in the array. If we could not find these values then it returns false for that particular entry . As the array is sorted, we can employ a binary search which takes O(log n) to find these calculated values.
If we could apply the same procedure from A[0] to A[n-1], we get a working algorithm. As the binary search is applied as many times as the number of elements in the array the time complexity is O(n log n).
The algorithm i have used is given below.
If you find any discrepancy or contradicting examples, please comment.
for i = 0 to n-1
{
x = A[i] +1;
y = A[i] -1;
if (binarysearch(x) == 1 || binarysearch(y) == 1)
{
return true;
break;
}
}
return false;