个人技术分享

代码实现：

int binary_search(int *arr, int n, int key) {
    int head = 0, tail = n - 1, mid;
    while (head <= tail) {
        mid = (head + tail) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[mid] > key) {
            tail = mid - 1;
        } else {
            head = mid + 1;
        }
    }
    return head;
}

void insert(int *arr, int n, int ind1, int ind2) {
    if (arr == NULL || ind1 < 0 || ind2 > n - 1 || ind1 >= ind2) {
        return;
    }
    int i, value = arr[ind2];
    for (i = ind2; i > ind1; i--) {
        arr[i] = arr[i - 1];
    }
    arr[i] = value;
}

double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size) {
    int n = nums1Size + nums2Size;
    int a[n];
    int i = 0, j;
    for (j = 0; j < nums1Size; j++) {
        a[i++] = nums1[j];
    }
    for (j = 0; j < nums2Size; j++) {
        a[i++] = nums2[j]; 
    }
    for (j = 1; j < n; j++) {
        if (a[j] < a[j - 1]) {
            insert(a, j + 1, binary_search(a, j, a[j]), j);
        }
    }
    if (n % 2 == 1) {
        return a[n / 2];
    } else {
        return 1.0 * (a[n / 2 - 1] + a[n / 2]) / 2;
    }
}