The most difficult thing is doing binary search among two sorted arrays, in this video Tushar Roy given us a straightforward method of how to do binary search among tow sorted arrays.

Assume we have two sorted arrays, X and Y, and cut them between at x2,x3 and y3,y4:

If we meet the conditions:

  • x2 <= y3
  • y2 <= x3

then we find the median postion, as the merged arrays of the four elements may be order by:

As above shows, in the left side: x1,y1,y2, and in the right side: x4,x5,y5. Both sides have the same number of elements, and in the left side are less than or equal those four elements, and in the right side are greater than or equal those four elements.