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

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;
}``````

• great!