I think Binary search with some modification can do this sucessfully.
The sequence for searching in the array will be like this:
Go to middle, check its left and right,
if both are different, then this is our element.
else we direct our search towards left or right as usual.
I don't think this will be skipping any elements, and it will successfully find the element in $O(logn)$.
@Tuhin Dutta check this. is this right?