Median of a Sorted Array in Kotlin

If the array has an odd number of elements, then the median is simply the middle element of the sorted array. If the array has an even number of elements, then the median is the average of the two middle elements of the sorted array.

Here is a sample Kotlin code to find the median of an array:

fun findMedian(sortedArray: IntArray): Double {
    val midIndex = sortedArray.size / 2

    return if (sortedArray.size % 2 == 0) {
        // Array has even number of elements
        (sortedArray[midIndex - 1] + sortedArray[midIndex]) / 2.0
    } else {
        // Array has odd number of elements
        sortedArray[midIndex].toDouble()
    }
}
fun main() {
    val sortedArray = intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9)
    val median = findMedian(sortedArray)

    println("Median of array: $median")
}

Here’s how the above code works:

1. We begin by computing the middle index midIndex of the sorted array using the formula sortedArray.size / 2.
2. Next, we check if the sorted array has an even number of elements by checking if its size is divisible by 2 with a zero remainder.
3. If the sorted array has an even number of elements, we compute the two middle elements using the indices midIndex - 1 and midIndex. We then compute their average using the formula (sortedArray[midIndex - 1] + sortedArray[midIndex]) / 2.0, and return the result.
4. If the sorted array has an odd number of elements, we simply return the element at the middle index midIndex, which is the median.

Note that this algorithm does not modify the input array, and works on any sorted array of integers.

The time complexity of the findMedian function for a sorted array is O(1), which means it takes a constant amount of time to compute the median, regardless of the size of the input array. This is because the function only performs a few basic arithmetic operations and array index lookups, which can be executed in constant time.

The space complexity of the function is O(1) as well, since the function only uses a few constant-sized variables to store the middle index and the computed median value. Therefore, the function uses a constant amount of memory, regardless of the size of the input array.