CareerCup

well , skip k - a[i] elements after each element and then search again ....
repeat till you find k

We can find mid if a[mid]<p and a[mid]>0 return mid;

else if a[mid]>p search left between 0 and mid else find between mid and p.

this is log(n) where n is length of array.

what's O(n/k) algo?

use binary search-> compare value of k with value of index mid and value at mid as follows:
if(a[mid]==k) return mid;
else
       if(k<mid)
              if(k>a[mid])
                    low=mid+1
              else
                   high=mid-1
      else //when k >=mid
           low=mid+1

well the binary search work just as it is..because, if K is greater than current mid then their must be an element on right of current mid which is equal to K otherwise the last element cannot be p (which is greater than K). Similarly if K is less than current mid there must be an element on left of current mid equal to K (otherwise the current mid cannot be greater than K). So apply binary search as follows:
if K is greater than current mid, compare K with mid element of right array and vice versa.

difference = MOD(arr[i]-k)

if difference = 0 then print else skip next difference elements
i+=difference

repeat till k is found or end of array is reached