题解 | #在两个长度相等的排序数组中找到上中位数#

方法一：遍历法，因数列单调递增，故数列1从左往右，数列2从右往左，则中位数出现的情况共2种，一是中位数在数列1和2均存在，则只需在遍历时找到相等的值即可；二是中位数有且仅存在一个，该类型分3种情况，一是遍历刚开始，若数列1最小数大于数列2最大数，则数列2的最大值为中值；二是遍历过程中，若数列1由刚开始的小于数列2的情况变为大于数列2，则中位数可能为此时数列2的对应元素或者上一轮对比中数列1中的元素，只需比较即可，谁大谁为中值；三是遍历结束后，仍无数列1大于数列2元素的情况，则说明中位数为数列1的最大值。
方法二：二分递归法，首先同遍历法一样排除第一种情况，即中位数在数列1和2均存在，然后寻找第二类情况的中位数，采用二分递归法寻找答案，分2种情况，一是中值在二分的边界上和在边界值之间。当在边界上时，表明已经经过多轮检索，排除了除此时边界上的所有情况，则只需要比较两个数列中的边界值和相邻值，共4个元素，其中第二小的值为中位数；二是在边界值中间，则只需要让数列1的中间值和数列2的待比较值互相介于对方相邻元素的值之间，然后在比较二者大小，小的则为中位数，若不满足互相介于为对方相邻元素的值之间的条件，则需要根据二者大小更新边界，若数列1大于数列2的元素，则说明中位值在数列1此时中间值的左边，左边界值不变，中间值更新为右边界值，否则右边界值不变，左边界更新为中间值，进行下一轮查询，直到找到中值。
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * find median in two sorted array
 * @param arr1 int整型一维数组 the array1
 * @param arr1Len int arr1数组长度
 * @param arr2 int整型一维数组 the array2
 * @param arr2Len int arr2数组长度
 * @return int整型
 */
 int JudgeSecond(int BorderBelow1,int BorderBelow2,int BorderUp1,int BorderUp2)
{
    int RetVal = -1;
    if(BorderBelow1 >= BorderUp2)
    {
        RetVal = BorderUp2;
    }
    else 
    {
        if(BorderBelow1 >= BorderBelow2)
        {
            RetVal = BorderBelow1;
        }
        else 
        {
            RetVal = BorderBelow2;
        }
    }
    if(BorderBelow2 >= BorderUp1)
    {
        RetVal = BorderUp1;
    }
    else 
    {
        if(BorderBelow2 >= BorderBelow1)
        {
            RetVal = BorderBelow2;
        }
        else 
        {
            RetVal = BorderBelow1;
        }
    }
    return RetVal;
}
void LookMedium(int ThLow1,int ThHigh1,int* arr1, int* arr2,int Num,int* RetVal)
 {
    int index = ThLow1 + (ThHigh1- ThLow1) / 2;
    printf("%d  %d %d\n",index,ThHigh1,ThLow1);
   if(*(arr1 + index) ==  *(arr2 + Num - 1 - index))
   {
        *RetVal = *(arr2 + Num - 1 - index);
        return;
   }
   else 
   {
        if(index == ThLow1)
        {
            *RetVal = JudgeSecond(*(arr1 + index),*(arr2 + Num - 1 - index - 1),*(arr1 + index + 1),*(arr2 + Num - 1 - index));
            return;
        }
        else if(index == ThHigh1)
        {
            *RetVal = JudgeSecond(*(arr1 + index -1),*(arr2 + Num - 1 - index),*(arr1 + index),*(arr2 + Num - index));
            return;
        }
        else 
        {
            if(*(arr1 + index) > *(arr2 + Num - 1 - index))
            {
                if((*(arr1 + index) > *(arr2 + Num - 1 - index - 1) ) && (*(arr1 + index) < *(arr2 + Num - index) )&& (*(arr1 + index + 1) > *(arr2 + Num - 1 - index) ) &&  (*(arr1 + index - 1) < *(arr2 + Num - 1 - index) ))
                {
                     *RetVal  = *(arr2 + Num - 1 - index);
                     return;
                }
                else {
                    LookMedium(ThLow1,index,arr1,arr2,Num,RetVal);
                }
            }
            else {
                if((*(arr1 + index) > *(arr2 + Num - 1 - index - 1) ) && (*(arr1 + index) < *(arr2 + Num - index) )&& (*(arr1 + index + 1) > *(arr2 + Num - 1 - index) ) &&  (*(arr1 + index - 1) < *(arr2 + Num - 1 - index) ))
                {
                     *RetVal  = *(arr1 + index);
                     return;
                }
                else {
                    LookMedium(index,ThHigh1,arr1,arr2,Num,RetVal);
                }
            }
        }
   }
 }
int findMedianinTwoSortedAray(int* arr1, int arr1Len, int* arr2, int arr2Len ) {
    // write code here
    int RetVal = -1;
    #if 1
    if(arr1Len == 1)
    {
        if(*arr1 > *arr2)
        {
            RetVal= *arr2;
        }
        else 
        {
            RetVal= *arr1;
        }
    }
    else {
        LookMedium(0, arr1Len - 1,arr1,arr2,arr1Len,&RetVal);
    }
    #else
    for(int i = 0; i < arr1Len; i++)
    {
        if(*(arr1+i) ==*(arr2+arr2Len -i -1))
        {
           RetVal = *(arr2+arr2Len -i -1);
                break;
        }
        else if(*(arr1+i) >*(arr2+arr2Len -i -1))
        {
            if(i == 0)
            {
                RetVal = *(arr2+arr2Len -i -1);
                break;
            }
            else {
                if(*(arr1+ i -1) >*(arr2+arr2Len -i -1))
                {
                    RetVal =*(arr1+ i -1) ;
                    break;
                }
                else {
                    RetVal = *(arr2+arr2Len -i -1);
                    printf("执行%d",i);
                    break;
                }
            }
        }
        else {
            
        }
    }
    if(RetVal ==-1 )
    {
        RetVal = *(arr1+arr1Len-1);
    }
    #endif
    return RetVal;
}