[LeetCode] 295. Find Median from Data Stream

😎풀이

1. 초기화 시 this.arr에 빈 배열 생성
2. addNum 메서드 호출 시 이진 탐색을 통해 적절한 위치에 입력
3. findMedian 메서드 호출 시 중앙값 반환

class MedianFinder {
    private arr: number[]
    constructor() {
        this.arr = []
    }

    addNum(num: number): void {
        let left = 0
        let right = this.arr.length - 1
        while (left <= right) {
            const mid = Math.floor((left + right) / 2)
            if (this.arr[mid] < num) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        this.arr.splice(left, 0, num) 
    }

    findMedian(): number {
        const isOdd = (this.arr.length & 1) === 1
        const mid = Math.floor(this.arr.length / 2)
        if(isOdd) {
            return this.arr[mid]
        } else {
            return (this.arr[mid - 1] + this.arr[mid]) / 2 
        }
    }
}