코딩 테스트 연습 - two sum2(input array is sorted)

01. 이해

오름차순으로 정렬된 정수 배열을 받아 서로 합쳤을 때 입력받은 숫자가 될 수 있는 원소 2개의 인덱스를 반환. 배열 안에서 답이 될 수 있는 케이스는 단 하나 존재하며, 같은 원소를 두번 더하는 것은 불가능함. 인덱스는 제로 베이스가 아니기 때문에 1부터 시작함.

02. 계획

배열의 원소를 순서대로 탐색해 첫번째 원소를 지정한 다름 그 원소와 더했을 때 타겟넘버가 될 수 있는 원소를 찾아야 함. 답안의 첫번째 원소를 A, 두번째 원소를 B라고 했을 때, 오름차순으로 정렬되어 있기 때문에 특정 인덱스의 원소를 A로 지정한 뒤 배열의 마지막 원소를 더했을 때의 값이 타겟 넘버보다 작으면 그 원소는 A가 될 수 없기 때문에 비교를 진행할 필요가 없음.

03. 실행

//use binarySearch method in kotlin
fun twoSum(numbers: IntArray, target: Int): IntArray {

    run loop@{
        numbers.forEachIndexed { index, i ->
            if (i + numbers.last() < target) {
                return@forEachIndexed
            }
            val findIndexResult = numbers
                .binarySearch(target - i, fromIndex = index + 1)

            if (findIndexResult > -1) {
                return intArrayOf((index + 1), (findIndexResult + 1))
            }

        }
    }
    return intArrayOf()
}

//use two pointer from edge side
fun twoSum2(numbers: IntArray, target: Int): IntArray {

    var elementAIndex = 0
    var elementBIndex = numbers.lastIndex

    while (elementAIndex < elementBIndex) {
        if (numbers[elementAIndex] + numbers[elementBIndex] == target) {
            return intArrayOf(elementAIndex + 1, elementBIndex + 1)
        }
        if (numbers[elementAIndex] + numbers[elementBIndex] > target) {
            elementBIndex -= 1
        }
        if (numbers[elementAIndex] + numbers[elementBIndex] < target) {
            elementAIndex += 1
        }
    }
    return intArrayOf()
}

//use binary search algorithm by own code
fun twoSum3(numbers: IntArray, target: Int): IntArray {

    run loop@{
        numbers.forEachIndexed { index, firstValue ->
           var startIndex = index + 1
            var lastIndex = numbers.size
            val secondValue = target - firstValue
            while (startIndex < lastIndex) {
                val pivot = startIndex + (lastIndex - startIndex) / 2
                when {
                    numbers[pivot] == secondValue -> return intArrayOf(index + 1, pivot + 1)
                    numbers[pivot] < secondValue -> startIndex = pivot + 1
                    else -> lastIndex = pivot
                }
            }

        }
    }
    return intArrayOf()
}

04. 회고

문제 자체는 어렵지 않았는데 모든 원소를 비교하니까 속도가 너무 느렸다. 그래서 생각해보니 정렬이 되어있는 배열이기 때문에 좀 더 효율적인 검색 방법이 있을 것 같아 찾아보고 binarySearch 메소드를 사용했더니 전체 답안 중 상위 50% 정도로 빨라졌다.
이쯤되니 그렇다면 나머지 상위 50%는 어떻게 했길래...라는 생각이 들어 binarySearch를 직접 구현해 보았다. 그랬더니 상위 98.43%까지 상승했다.
kotlin의 binarySearch와 왜 이렇게 속도 차이가 나는지 궁금해서 java.util.Arrays.binarySearch 소스를 까봤는데 별다를 건 없었다. 메소드 자체가 intArray가 아닌 제네릭을 파라미터로 받을 수 있게 되어 있어서 그런걸까?