二分法——寻找两个正序数组的中位数

二分法又称折半查找，应用于有序数组查找，时间复杂度为log(n)

1.从数组中间开始搜，如果该元素刚好是目标元素则结束搜索过程。
2.如果该元素大于或者小于该元素，则从元素左边或者右边再次二分。
3.如果某一步数组为空，则表明找不到该元素。
代码如下：

// 循环版
    public int findK(int[] nums,int target){
        int left = 0;
        int right = nums.length;
        while (left=right) return -1;
        if(target < nums[mid]){
            return findK(nums,left,mid-1,target);
        }else {
            return findK(nums,mid+1,right,target);
        }
    }

二分排序属于一种改进了的插入排序 稳定排序 时间负责度为O（n*n）

public void findKSort(int[] nums){
        int i = 0;
        int low,high,mid;
        for( i = 1;itemp){
                    high = mid-1;
                }else {
                    low = mid+1;
                }
            }
            for(int j =i-1;j>high;j--){
                nums[j+1]=nums[j];
            }
            nums[high+1] = temp;
        }

        for (i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }

题目：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。找出并返回这两个正序数组的 中位数 。
例：[2,3] [3,4]
答：3.0000

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
   int len1 = nums1.length;
   int len2 = nums2.length;

   int mid1 = (len1+len2+1)/2;//找到第一个中位数
   int mid2 = (len1+len2+2)/2;//找到第二中位数  若只有一个中位数则mid1=mid2
   return (findKth(nums1,0,nums2,0,mid1)+findKth(nums1,0,nums2,0,mid2))/2.0;

    }

    int findKth(int[] nums1,int i,int[] nums2,int j,int k){//在两个数组中找到位置在k的数
    if(nums1.length<=i){return nums2[j+k-1];}
    if(nums2.length<=j){return nums1[i+k-1];}
    if(k == 1){
        return nums1[i]