https://leetcode.com/problems/median-of-two-sorted-arrays

median-of-two-sorted-arrays.java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // search range solution
        int len = nums1.length + nums2.length;
        double mid = -1;
        if (len % 2 == 1) {
             mid = findKth(nums1, nums2, (len + 1) /2 );
        } else {
            int mid1 = findKth(nums1, nums2, len / 2);
            int mid2 = findKth(nums1, nums2, len / 2 + 1);
            mid = (mid1 + mid2) / 2.0;
        }
        return mid;
    }
    
    private int findKth(int[] nums1, int[] nums2, int k) {
        if (nums1.length == 0) {
            return nums2[k - 1];
        } else if (nums2.length == 0) {
            return nums1[k - 1];
        }
        int len1 = nums1.length;
        int len2 = nums2.length;
        int l = Math.min(nums1[0], nums2[0]);
        int h = Math.max(nums1[len1 - 1], nums2[len2 - 1]);
        
        int lp1 = 0; // left ptr
        int rp1 = len1 - 1; // right ptr
        
        int lp2 = 0;
        int rp2 = len2 - 1;
        
        while(l < h) {
            int mid = l + (h - l) / 2;
            //System.out.println(mid);
            int idx1 = getIndex(nums1, lp1, rp1, mid);
            //System.out.println(idx1);
            int idx2 = getIndex(nums2, lp2, rp2, mid);
            //System.out.println(idx2);
            int count = idx1 + idx2;
            
            if (count >= k) {
                h = mid;
                // mid larger or equal to target, can continue to left space
                // next mid: mid_next should be equal or less than mid
                rp1 = idx1;
                rp2 = idx2;
            } else {
                l = mid + 1;
                // mid less than target, can continue to right space
                // next mid: mid_next should be equal or greater than mid
                lp1 = idx1;
                lp2 = idx2;
            }
        }
        return l;
    }
    
    private int getIndex(int[] nums, int l, int r, int target) {
        // find insert position, binary search index
        while(l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l < nums.length && nums[l] <= target) {
            return l + 1;
        }
        return l;
    }    
}