Share my O(log(m+n)) iterative solution


  • 5
    L

    Let's first start with the special case:

    m = 0 or n = 0:

    In such case, simple return

    m%2==1 ? A[m/2] : (A[m/2-1]+A[m/2])/2.0;
    

    Or

    n%2==1 ? B[n/2] : (B[n/2]+B[n/2-1])/2.0;
    

    The total number of numbers is m+n, therefore, if (m+n)%2==1, we need to find the (m+n)/2-th element; otherwise, we need to find both ((m+n)/2)-th and ((m+n)/2-1)-th elements.

    So the key is to implement the following function:

    int find(int A[], int m, int B[], int n, int k) {}
    

    which is: find the k-th element in either A or B.

    Since the element can exist in either A or B, let's implement the following function:

    int _find(int A[], int m, int B[], int n, int k, bool* found) {}
    

    This function tries to find k-th element in A. If this function is ready, we can do the search by calling:

    bool found = false;
    int v = _find(A, m, B, n, k, &found);  // Try to search in A.
    return found ? v : _find(B, n, A, m, k, &found);  // Search in B.
    

    So, let's focus on implementing the function int _find(int A[], int m, int B[], int n, int k, bool* found) {}

    This is a typical binary search, with some edge cases we need to consider.

    int _find(int A[], int m, int B[], int n, int k, bool* found) {
    if (k==0) {
    *found = true;
    return A[0]<=B[0] ? A[0] : B[0];
    }

        int l=0, h=m-1;
        while (l<=h) {
            int mid=l+(h-l)/2;  // A[mid], mid elements at the left side in A.
            // k-mid elements at the left side in B.
            if (k-mid<0) {
                h=mid-1;
            } else if (k-mid==0) {
                if (B[0]>=A[mid]) {
                    *found = true;
                    return A[mid];
                } else {
                    h=mid-1;
                }
            } else if (k-mid>n) {
                l=mid+1;
            } else if (k-mid==n) {
                if (A[mid] >= B[n-1]) {
                    *found = true;
                    return A[mid];
                } else {
                    l=mid+1;
                }
            } else {
                if (A[mid] >= B[k-mid-1] && A[mid] <= B[k-mid]) {
                    *found = true;
                    return A[mid];
                } else if (A[mid] < B[k-mid-1]) {
                    l=mid+1;
                } else {
                    h=mid-1;
                }
            }
        }
        *found = false;
    }

  • 0
    Q

    great!
    your tutorial is very clear and helpful


  • 0
    I

    thanks for your great tutorial.


  • 0
    T

    I think this solution is O(log(m*n)), since both A and B might be searched and the algorithm only deals with one of them at a time.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.