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

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, l=0, r=0, m;
    cin>>n;
    int a[n], b[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    while(l+r<n){
        if(l<n && r<n)
            m = (a[l]<b[r] ? a[l++]: b[r++]);
        else if(l<n)
            m = a[l++];
        else
            m = b[r++];
    }
    cout<<m<<endl;
    return 0;
}

import java.util.Scanner;
 
/**
 * @author zhuqiu
 * @date 2020/4/8
 */
public class Main {
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        int[] nums1 = new int[len];
        int[] nums2 = new int[len];
        for (int i = 0; i < len; i++) {
            nums1[i] = in.nextInt();
        }
        for (int i = 0; i < len; i++) {
            nums2[i] = in.nextInt();
        }
        Main instance = new Main();
        int result = instance.findMedianSortedArrays(nums1, nums2);
        System.out.println(result);
    }
 
    public int findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
 
        return findKth(nums1, 0, nums2, 0, left);
    }
 
    public int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length) return nums2[j+k-1];
        if (j >= nums2.length) return nums1[i+k-1];
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        int midValue1 = (i + k/2 -1 < nums1.length) ? nums1[i + k/2 -1] : Integer.MAX_VALUE;
        int midValue2 = (j + k/2 -1 < nums2.length) ? nums2[j + k/2 -1] : Integer.MAX_VALUE;
        if (midValue1 < midValue2) {
            return findKth(nums1, i + k/2, nums2, j, k - k/2);
        } else {
            return findKth(nums1, i, nums2, j + k/2, k - k/2);
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>arr1(n),arr2(n),arr(n);
    for(int i=0;i<n;i++)
        cin>>arr1[i];
    for(int i=0;i<n;i++)
        cin>>arr2[i];
    int j=0,j1=0,j2=0;
    while(j<n&&j1<n&&j2<n)
    { 
        if(arr1[j1]<=arr2[j2])
        {
            arr[j]=arr1[j1];
            j++;
            j1++;
        }
        else if(arr1[j1]>arr2[j2])
        {
            arr[j]=arr2[j2];
            j++;
            j2++;
        }
    }
    cout<<arr[n-1]<<endl;
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int num=2*n;
        int[] arr=new int[num];
        for(int i=0;i<num;i++){
            arr[i]=sc.nextInt();
        }
        Arrays.sort(arr);
        int sum=n/2;
        if(0==sum){
            System.out.print(arr[sum]);
        }else{
            System.out.print(arr[n-1]);
        }
    }
    
}

#include<iostream>
#include<limits.h>
#include<vector>

using namespace std;

class Solution{
  public:
      int find(vector<int> nums1,vector<int> nums2,int k){
        if(k < 1 || k > nums1.size() + nums2.size())
           return -1;
       
        int n = nums1.size();
        int m = nums2.size();
        int low = max(0,k-m);
        int high = min(n,k);
         //确定i的范围
        while(low < high){
            int mid = low + (high - low)/2;
            if(nums2[k-mid-1] > nums1[mid]){//这里的m=i，j=k-m,所以i+j=k，k-m-1相当于j-1即j前一个位置。j-1比i位置的值大，a数组i的位置往右移
                low = mid + 1;
            }else{
                high = mid;
            }
        }
        
        //判断low 是否为 0 或者为k 否者 第k个数为 max(num1[low-1] + num1[k-low -1]));
        int num1leftmax = low==0?INT_MIN:nums1[low-1];
        int num2leftmax = low==k?INT_MIN:nums2[k-low-1];
        
        return max(num1leftmax,num2leftmax);

    }
};

int main(){
    int N,K;
    cin>>N;
    vector<int> arr1(N);
    for(int i=0;i<N;i++){
        cin>>arr1[i];
    }
    vector<int> arr2(N);
    for(int i=0;i<N;i++){
        cin>>arr2[i];
    }
    Solution c1;
    cout<<c1.find(arr1,arr2,N)<<endl;
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int getUpmid(vector<int> a, int s1, int e1, vector<int> b, int s2, int e2){
    int mid1 = 0;
    int mid2 = 0;
    int offset = 0;
    while(s1 < e1){
        mid1 = s1+((e1-s1)>>1);
        mid2 = s2+((e2-s2)>>1);
        offset = ((e1 - s1 + 1) & 1) ^ 1;
        if(a[mid1] > b[mid2]){
            e1 = mid1;
            s2 = mid2 + offset;
        } else if(a[mid1] < b[mid2]){
            s1 = mid1 + offset;
            e2 = mid2;
        } else{
            return a[mid1];
        }
    }
    return min(a[s1], b[s2]);
}

int main(){
    int n; scanf("%d", &n);
    vector<int> a(n), b(n);
    for(int i=0; i<2*n; i++){
        if(i<n) scanf("%d", &a[i]);
        else scanf("%d", &b[i-n]);
    }
    int ans = getUpmid(a, 0, n-1, b, 0, n-1);
    cout << ans;
    return 0;
}