Solution: 
we can extend binary search to intervals.(Assuming the intervals are sorted)
consider interval [a,b].
if (a-x)(b-x) <=0 
then x belongs to [a,b].
else
if x>a 
element can be present only in the intervals to its right. 
so select the middle interval among them to it’s right
and repeat the procedure.
else
element can be present only in the intervals to its left. 
so select the middle interval among them to it’s left
and repeat the procedure.

The complexity of this problem is log(N) where N is the number of sorted non-overlapping intervals.

Solution: 
If the above intervals are overlapping ,then they can be merged in O(N) and then the exact intervals can be resolved later.Otherwise ,we can identify one correct interval and then linear search on its left and right neighbourhood to find the other solutions.

Algorithm  is explained:

Given an input array of size n. Random sort is sampling
a new array from the given array and check whether the
sampled array is sorted or not. If sorted return else
sample again. The stress was on the
code.