leetcode4

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)).

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 使用二分搜索

package leetcode; public class leetcode4 { class Solution {    public double findMedianSortedArrays(int[] nums1, int[] nums2) {     int m=nums1.length;//nums1的长度     int n=nums2.length;//nums2的长度     if(m>n)//保证n<m   当i=0~m时，j=(m+n+1)/2-i,可能为负数     {     int[] temp=nums1;nums1=nums2;nums2=temp;     int tmp=m;m=n;n=tmp;     }     int imin=0,imax=m,halflen=(m+n+1)/2;     while(imin<=imax)     {     int i=(imin+imax)/2;//i,j初始化     int j=halflen-i;//nums2[j-1]<=nums1[i]&&nums2[j]>=nums1[i-1]时满足条件其他都要分类讨论。             if(i<imax&&nums2[j-1]>nums1[i])    //第一种情况     {     imin=imin+1;     }     else if(nums2[j]<nums1[i-1]&&i>imin)//第二种情况     {     imax=imax-1;     }     else //第三种情况     {        int maxleft=0;     int minright=0;     if(i==0) { //考虑四种边界情况     maxleft=nums2[j-1];     }     else if(j==0) {     maxleft=nums1[i-1];     }     else {     maxleft=Math.max(nums1[i-1], nums2[j-1]);     }     if((m+n)%2==1)return maxleft;     if(i==m) {minright=nums2[j];}     else if(n==j) {     minright=nums1[i];     }     else {     minright=Math.min(nums1[i], nums2[j]);     }     return (maxleft+minright)/2;     }     }            return 0.0;    } } }