It can be logn. First look for num - 1, get n1, then look for num + 1, get n2. Here comes a trick. Here is the binary search we should use, while(start <= end){ // do what normal binary search should do. } //if num - 1 or num + 1 is not in the array. return start - 1;

binary search in logN

Worst case can not be log(n) since the number of occurrence is asked. You can find the exact place you have to start with binary search but you have to count occurrence as well. If the array has only one distinct element, you have to go over the whole array which becomes O(n) in the worst case.