Median of Two Sorted Arrays | Improved Solution

find-median-sorted-arrays-improved.cs

public class Solution 
{
    public double FindMedianSortedArrays(int[] A, int[] B) 
    {
        if (Object.ReferenceEquals(A, null) || Object.ReferenceEquals(B, null))
        {
            throw new ArgumentNullException();
        }

        int aLen = A.Length;
        int bLen = B.Length;

        // Make sure we always search the shorter array.
        if (aLen > bLen)
        {
            Swap(ref A, ref B);
            Swap(ref aLen, ref bLen);
        }

        int leftHalfLen = (aLen + bLen + 1) / 2;

        // Since A is guaranteed to be either shorter or of
        // the same length as B, we know it can contribute 
        // 0 or all of its values to the left half of A ∪ B.
        int aMinCount = 0;
        int aMaxCount = aLen;

        while (aMinCount <= aMaxCount)
        {
            int aCount = aMinCount + ((aMaxCount - aMinCount) / 2);
            int bCount = leftHalfLen - aCount;

            //
            // x can be null if A is not contributing any values to left half.
            // e.g. A = [10, 11], B = [3, 4] 
            //  ⟹ left half = [3, 4], aCount = 0, bCount = 2.
            //
            int? x = (aCount > 0) ? A[aCount - 1] : (int?)null;

            //
            // y can be null if B is not contributing any values to left half.
            // e.g. A = [3, 4], B = [10, 11] 
            //  ⟹ left half = [3, 4], aCount = 2, bCount = 0.
            //
            int? y = (bCount > 0) ? B[bCount - 1] : (int?)null;

            //
            // xP can be null if A is contributing all of its values to left half, 
            //  i.e. aCount = A.Length.
            // e.g. A = [3, 4], B = [10, 11] 
            //  ⟹ left half = [3, 4], aCount = 2, bCount = 0.
            //
            int? xP = (aCount < aLen) ? A[aCount] : (int?)null;

            //
            // yP can be null if B is contributing all of its values to left half, 
            // i.e. bCount = B.Length.
            // e.g. A = [10, 11], B = [3, 4] 
            //  ⟹ left half = [3, 4], aCount = 0, bCount = 2.
            //
            int? yP = (bCount < bLen) ? B[bCount] : (int?)null;

            if (x > yP)
            {
                // Decrease A's contribution size; x lies in the right half.
                aMaxCount = aCount - 1;
            }
            else if (y > xP)
            {
                // Decrease B's contribution size, i.e. increase A's contribution size; 
                // y lies in the right half.
                aMinCount = aCount + 1;
            }
            else
            {
                //
                // Neither x nor y lie beyond the left half. We found the right aCount.
                // We don't know how x and y compare to each other yet though.
                //

                //
                // If aLen + bLen is odd, the median is the greater of x and y.
                // Remember that either x or y can be null (if A or B is not contributing).
                //
                int leftHalfEnd = (x == null) 
                                    ? y.Value 
                                    : (y == null) 
                                        ? x.Value 
                                        : Math.Max(x.Value, y.Value);

                if (IsOdd(aLen + bLen))
                {
                    return leftHalfEnd;
                }

                //
                // aLen + bLen is even. To compute the median, we need to find 
                // the first element in the right half, which will be the smaller 
                // of xP and yP. Remember that either xP or yP can be null (if all 
                // the values of A or B are in the left half).
                //
                int rightHalfStart = (xP == null) 
                                        ? yP.Value 
                                        : (yP == null) 
                                            ? xP.Value 
                                            : Math.Min(xP.Value, yP.Value);
                return (leftHalfEnd + rightHalfStart) / 2.0;
            }
        }

        throw new InvalidOperationException("Unexpected code path reached");
    }

    private void Swap<T>(ref T x, ref T y)
    {
        T temp = x;
        x = y;
        y = temp;
    }

    // The least significant bit of any odd number is 1.
    private bool IsOdd(int x) => (x & 1) == 1;
}