1. /**
    2.  * 4. Median of Two Sorted Arrays
    3.  * <p>
    4.  * Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
    5.  * <p>
    6.  * The overall run time complexity should be O(log (m+n)).
    7.  * <p>
    8.  * Example 1:
    9.  * <p>
    10.  * Input: nums1 = [1,3], nums2 = [2]
    11.  * Output: 2.00000
    12.  * Explanation: merged array = [1,2,3] and median is 2.
    13.  * Example 2:
    14.  * <p>
    15.  * Input: nums1 = [1,2], nums2 = [3,4]
    16.  * Output: 2.50000
    17.  * Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
    18.  * Example 3:
    19.  * <p>
    20.  * Input: nums1 = [0,0], nums2 = [0,0]
    21.  * Output: 0.00000
    22.  * Example 4:
    23.  * <p>
    24.  * Input: nums1 = [], nums2 = [1]
    25.  * Output: 1.00000
    26.  * Example 5:
    27.  * <p>
    28.  * Input: nums1 = [2], nums2 = []
    29.  * Output: 2.00000
    30.  * <p>
    31.  * <p>
    32.  * Constraints:
    33.  * <p>
    34.  * nums1.length == m
    35.  * nums2.length == n
    36.  * 0 <= m <= 1000
    37.  * 0 <= n <= 1000
    38.  * 1 <= m + n <= 2000
    39.  * -106 <= nums1[i], nums2[i] <= 106
    40.  */
    41. public class Lesson4 {
    43.     public static void main(String[] args) {
    44.         int[] nums1 = {1, 2};
    45.         int[] nums2 = {3, 4};
    47.         Util.println(new Solution().process(nums1, nums2));
    48.         //System.out.println(new Solution().process(nums1, nums2));
    49.     }
    51.     private static class Solution {
    53.         double process(int[] array1, int[] array2) {
    54.             int[] arrayM = array1;
    55.             int[] arrayN = array2;
    56.             if (array1.length > array2.length) {
    57.                 arrayM = array2;
    58.                 arrayN = array1;
    59.             }
    61.             int m = arrayM.length;
    62.             int n = arrayN.length;
    64.             int min = 0;
    65.             int max = m;
    66.             int half = (m >> 1) + (n >> 1);
    67.             while (min <= max) {
    68.                 int i = (min >> 1) + (max >> 1);
    69.                 int j = half - i;
    70.                 if (min < i && arrayM[i] < arrayN[j - 1]) {
    71.                     min = i + 1;
    72.                 } else if (i > min && arrayM[i - 1] > arrayN[j]) {
    73.                     max = i - 1;
    74.                 } else {
    75.                     int maxLeft = 0;
    76.                     if (i == 0) {
    77.                         maxLeft = arrayN[j - 1];
    78.                     } else if (j == 0) {
    79.                         maxLeft = arrayM[i - 1];
    80.                     } else {
    81.                         maxLeft = Math.max(arrayN[j - 1], arrayM[i - 1]);
    82.                     }
    83.                     if ((m + n) / 2 == 1) {
    84.                         return maxLeft + 0.0;
    85.                     }
    87.                     int minRight = 0;
    88.                     if (i == m) {
    89.                         minRight = arrayN[j];
    90.                     } else if (j == n) {
    91.                         minRight = arrayM[i];
    92.                     } else {
    93.                         minRight = Math.min(arrayN[j], arrayM[i]);
    94.                     }
    96.                     return (maxLeft + minRight) / 2.0;
    97.                 }
    98.             }
    100.             return 0.0;
    101.         }
    103.     }
    105. }