求两个升序序列的中位数（减治法）

逃离我推掉我的手 2023-10-01 21:25 25阅读 0赞

#### 题目： ####

一个长度为L(L≥1)的升序序列S，处在第L/2（若为小数则去掉小数后加1）个位置的数称为S的中位数。例如，若序列S1=(11，13，15，17，19)，则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则S1和S2的中位数是11。现有两个等长升序序列A和B，试实现一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

#### 解题图解： ####

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_12_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_13_color_FFFFFF_t_70_g_se_x_16][]

#### 代码： ####

public class SearchMid {
        public static void main(String[] args) {
            int arr1[] = {11, 13, 15, 17, 19};
            int arr2[] = {2, 4, 6, 8, 20};
    
            System.out.println("中位数:"+searchMid(arr1, arr2, arr1.length - 1));
    
        }
    
        private static int searchMid(int[] arr1, int[] arr2, int n) {
            int start1 = 0, start2 = 0, end1 = n, end2 = n, mid1 = 0, mid2 = 0;
    
    
            while (end1 > start1 && end2 > start2) {
                mid1 = (start1 + end1) / 2;
                mid2 = (start2 + end2) / 2;
    
    
                if (arr1[mid1] == arr2[mid2]) {
                    return arr1[mid1];
                }
                if (arr1[mid1] < arr2[mid2]) {
    //                if ((end1-start1)%2==0){
    //                    start1=mid1;
    //                }
    //                else{
    //                    start1=mid1+1;
    //                }
    
                    start1 = (end1 - start1) % 2 == 0 ? mid1 : mid1 + 1;
                    end2 = mid2;
                } else {
                    end1 = mid1;
                    start2 = (end2 - start2) % 2 == 0 ? mid2 : mid2 + 1;
    //                if ((end2-start2)%2==0){
    //                    start2=mid2;
    //                }
    //                else {
    //                    start2=mid2+1;
    //                }
    
    
                }
    
    
            }
    
            return arr1[start1] > arr2[start2] ? arr2[start2] : arr1[start1];
    
    //        if (arr1[start1]>arr2[start2]){
    //            return arr2[start2];
    //        }
    //        else  return arr1[start1];
    
    
        }
    
    
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_12_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/a7d931b7b87a40bfb9c9b5ad582acc57.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_12,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4bd0816f06164b9f8dee582decbef777.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_13,color_FFFFFF,t_70,g_se,x_16