What is a half of an array and how to determine it…

Half of the array (or the "median" of the array if it is sorted) is the element that, if the array is sorted, divides it into two parts: elements less than or equal to the median and elements greater than or equal to the median. If the number of elements is even, the median is often considered as the arithmetic mean of the two central elements. In the context of "half of the array" in interview tasks, it can also imply finding the majority element, which appears more than N/2 times, where N is the number of elements in the array.

The definition of half of the array depends on the context:

Median (for a sorted array or when searching for the k-th smallest element):
- Sort the array.
- If the size N is odd, the median is the element at index N/2.
- If the size N is even, the median is the arithmetic mean of the elements at indices N/2 - 1 and N/2.
Majority element (an element that appears > N/2 times):
- Use the Boyer–Moore majority vote algorithm.
- Create variables candidate and count.
- Iterate through the array. If the current element equals candidate, increment count. If not, and count > 0, decrement count. If count = 0, set the current element as the new candidate, and set count to 1.
- After the first pass, candidate is a potential majority element. To ensure it actually appears more than N/2 times, a second pass is needed to verify.

Example of finding the median (in Swift):

// Sorting to find the median
func findMedian(in array: [Int]) -> Double? {
    guard !array.isEmpty else { return nil }

    let sortedArray = array.sorted()
    let n = sortedArray.count

    if n % 2 == 1 {
        return Double(sortedArray[n / 2])
    } else {
        return Double(sortedArray[n / 2 - 1] + sortedArray[n / 2]) / 2.0
    }
}

Example of finding the majority element (in Swift):

// Boyer–Moore voting algorithm
func findMajorityElement(in array: [Int]) -> Int? {
    var candidate: Int? = nil
    var count = 0

    for element in array {
        if count == 0 {
            candidate = element
            count = 1
        } else if element == candidate {
            count += 1
        } else {
            count -= 1
        }
    }

    // Verify if candidate is actually a majority
    var realCount = 0
    if let candidate = candidate {
        for element in array {
            if element == candidate {
                realCount += 1
            }
        }
        if realCount > array.count / 2 {
            return candidate
        }
    }

    return nil // No majority element
}

It is important to clarify with the interviewer which specific type of "half of the array" is meant in the context of the task.

What is a half of an array and how to determine it?