leetCode 4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

基本思路是：

　　每次从num2中取边界内[low2,high2)的中间数mid2，查找该数在num1中的位置loc，计算loc左边和mid2左边的数的个数，判断mid2是否是计算中位数需要的数。

　　由于每次是折半（num2中使用），且使用二分查找(num1中使用)，故其时间复杂度为log(m+n)。

　　每次取第二个数组的中间数mid2，故需要记录第二个数组的范围，即low2，high2（mid2=（low2+high2）/2），在第一个数组中利用二分查找查找mid2，二分查找的结果是一个范围：若找到，则返回的是mid2的位置，否则返回的是[l,r]，其中（num1[l]<mid2<num1[r]）满足l=r-1;

　　计算num1中 l 左边(包括 l 位置)和mid2左边(包括mid2)的数字的个数res，

　　若res==totalLength/2 且 totalLength为偶数，则中位数一定是两个数(left，right)的平均数，又因为 l 位置(包括 l 位置)左边和mid2(不包括mid2)左边的数都<=mid2，故mid2一定是left，right要么是num1中r位置的数(若该下标存在),要么是mid2右边的数(若存在)。

　　另外还有其他情况，这里不做分析。

　　主要是越界的判断有些繁琐，我觉得这恰恰是一种调试技巧，编程时尽可能的考虑每一种情况，即使意识到这种情况可能不存在，也要留出语句做判断，这在调试的时候会很省劲，因为可能自己意识错误。

  1 class Solution {
  2     class Pair {
  3         int mid1;
  4         int mid2;
  5 
  6         public Pair(int mid1, int mid2) {
  7             this.mid1 = mid1;
  8             this.mid2 = mid2;
  9         }
 10     }
 11 
 12     public Pair binarySearch(int[] a, int target) {
 13         int low = 0, high = a.length, mid = (low + high) / 2;
 14         while (low <= high && low < a.length) {
 15             mid = (low + high) / 2;
 16             if (a[mid] == target) {
 17                 while (mid<a.length-1 && a[mid+1]==target) ++mid;
 18                 return new Pair(mid, mid);
 19             } else if (target < a[mid]) {
 20                 high = mid - 1;
 21             } else {
 22                 low = mid + 1;
 23             }
 24         }
 25         Pair pair = null;
 26         if (low == mid) {
 27             if (mid > high) {
 28                 int t = mid;
 29                 mid = high;
 30                 high = t;
 31             }
 32             pair = new Pair(mid, high);
 33         } else {
 34             if (low > mid) {
 35                 int t = low;
 36                 low = mid;
 37                 mid = t;
 38             }
 39             pair = new Pair(low, mid);
 40         }
 41         return pair;
 42     }
 43 
 44     public double result(int[] nums1, int low1, int high1, int[] nums2, int low2, int high2) {
 45         int totalLength = nums1.length + nums2.length;
 46         int mid1, mid2;
 47         int right = -1, left = -1;
 48         boolean isOdd = (totalLength % 2 == 0) ? false : true;
 49 
 50         while (low2 <= high2 && low2< nums2.length && high2<= nums2.length) {// && res <= totalLength / 2
 51             mid2 = (low2 + high2) / 2;
 52             Pair pair = binarySearch(nums1, nums2[mid2]);
 53             int res = pair.mid1 + 1 + mid2 + 1;
 54             if (res == totalLength / 2) {
 55                 if (!isOdd) { //总个数为偶数
 56                     if (pair.mid1 > 0) {
 57                         if (pair.mid1 + 1 >= nums1.length) {
 58                             if (mid2 == nums2.length - 1) {
 59                                 System.out.println("目测这种情况不会发生1");
 60                             } else {
 61                                 return (nums2[mid2]+nums2[mid2+1])/2.0;
 62                             }
 63                         } else {
 64                             if (mid2 == nums2.length - 1) {
 65                                 return (nums2[mid2] + nums1[pair.mid1+1])/2.0;
 66                             } else {
 67                                 left = nums2[mid2];
 68                                 right = (nums1[pair.mid1 + 1] > nums2[mid2 + 1]) ? nums2[mid2 + 1] : nums1[pair.mid1 + 1];
 69                             }
 70                         }
 71                         return (left + right) / 2.0;
 72                     } else {
 73                         if (mid2 >= 0 && mid2 < nums2.length) {
 74                             left = nums2[mid2];
 75                             if (mid2+1>=nums2.length){
 76                                 right= nums1[pair.mid1+1];
 77                             }else {
 78                                 right= nums1[pair.mid1+1] > nums2[mid2+1]?nums2[mid2+1]:nums1[pair.mid1+1];
 79                             }
 80                         } else {
 81                             System.out.println("目测这种情况不会发生3");
 82                         }
 83                         return (left + right) / 2.0;
 84                     }
 85                 } else { // 总个数为奇数
 86                     if (pair.mid1+1< nums1.length){
 87                         if (nums2.length==1){
 88                             return nums1[pair.mid1+1];
 89                         }
 90                         if (mid2+1< nums2.length){
 91                             return nums1[pair.mid1+1] < nums2[mid2+1]?nums1[pair.mid1+1]:nums2[mid2+1];
 92                         }else {
 93                             return nums1[pair.mid1+1];
 94                         }
 95                     }else {
 96                         return nums2[mid2+1];
 97                     }
 98                 }
 99             }
100             if (res == totalLength / 2 + 1) {
101                 if (!isOdd) { // 总个数为偶数
102                     if (pair.mid1 == -1){
103                         return (nums2[mid2]+nums2[mid2-1])/2.0;
104                     }else {
105                         if (mid2-1>=0) {
106                             left = (nums1[pair.mid1] > nums2[mid2 - 1]) ? nums1[pair.mid1] : nums2[mid2 - 1];
107                             right = nums2[mid2];
108                             return (left + right) / 2.0;
109                         }else {
110                             left = pair.mid1;
111                             right = mid2;
112                             return (nums1[left] + nums2[right]) / 2.0;
113                         }
114                     }
115                 } else { // 总个数为奇数
116                     return nums2[mid2];
117                 }
118             }
119             if (res<totalLength/2+1){
120                 low2=mid2+1;
121             }else {
122                 high2=mid2-1;
123             }
124         }
125         return -1.0;
126     }
127 
128     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
129         /**
130          * 当某个数组为空时单独判断
131          * */
132         int left=-1,right=-1;
133         if (nums1.length==0){
134             if (nums2.length==0){
135                 System.out.println("目测这种情况不会发生5");
136             }else {
137                 if (nums2.length%2==0){
138                     left=nums2[nums2.length/2-1];
139                     right=nums2[nums2.length/2];
140                     return (left+right)/2.0;
141                 }else {
142                     return nums2[nums2.length/2];
143                 }
144             }
145         }
146         if (nums2.length==0){
147             if (nums1.length==0){
148                 System.out.println("目测这种情况不会发生6");
149             }else {
150                 if (nums1.length%2==0){
151                     left=nums1[nums1.length/2-1];
152                     right=nums1[nums1.length/2];
153                     return (left+right)/2.0;
154                 }else {
155                     return nums1[nums1.length/2];
156                 }
157             }
158         }
159         if (nums1.length==1 && nums2.length==1){
160             return (nums1[0]+nums2[0])/2.0;
161         }
162         double res = result(nums1, 0, nums1.length, nums2, 0, nums2.length);
163         if (res == -1)
164             return result(nums2,0,nums2.length,nums1,0, nums1.length);
165         return res;
166     }
167 }