In binary search complexity is O(logn ) because after visiting middle element you have to go either left or right but in this ques you have to traverse both left and right.
one solution can be using the algo of counting sort find the array B (that represents frequency of elements).{i hope you know about counting sort), then search for 1 in B.
or you can traverse each element linearly and checking if either of its left or right are equal to that element. if not then you have find ur required element.