Two sorted list, each of length n.
Another point is both are mutually exclusive , means every element of one list is different from every element of other list.
- So, first do binary search on list1
- if element is found then stop
here maximum comparison will be log n
- if element not found , go to second list and find element in log n time
So,total number of comparison O(2log n)=O(log n)