[코딩테스트] 이진탐색

말만 어려울 뿐이지 사실 이진탐색이라는 말은 2개로 쪼개서 검색하겠다는 얘기이다. 하지만 필요조건이 있다.

1. 데이터는 "정렬"되어 있어야 한다.

데이터가 정렬되지 않은 상태에서는 이진탐색이 의미가 없다...

가령 [1,5,3,64,6,8,3,12] 의 배열을 생각해보자.

이진탐색은 배열에서 왼쪽 인덱스와 오른쪽 인덱스를 설정하고, 그 중간값이 찾고자 하는 값과의 대소비교를 통해 해당 왼쪽/오른쪽 인덱스를 그 중간값으로 취하여 절반으로 줄여나가는 검색법이다.

하지만 해당 배열에서는 중간값이 의미가 없다. 중간값이 64나 6인데, 대소 비교의 의미가 없기 때문이다. 그러므로 무조건 데이터는 정렬되어 있어야 한다.

처음 내가 구현했던 코드이다.

 function binarySearch(arr,val){
    let left = 0
    let right = arr.length-1
    if(arr[left]==val) {
        return left
    } else if (arr[right] == val) {
        return right
    } else if (!arr[val]) {
        return -1
    }
    let result;
    while(true) {
        let middle = Math.floor((left+right)/2)
        if(arr[middle] == val) {
            result = middle
            break
        } else if (arr[middle] > val) {
            right = middle
        } else {
            left = middle
        }
    }
    return result
}

앞에서 예외처리?를 해주었다. 일단 인덱스가 left나 right 값인 경우엔 바로 그 인덱스를 반환해주었고, includes 함수를 써서 없는 경우엔 return을 시켰다.

근데 이게 바보같은 짓이라는 것을 알겠는가? includes도 사실 선형 검색이기 때문에 O(N)에 해당되는 시간 복잡도가 소요된다. 그럴꺼면 indexOf 함수를 쓰지 굳이 앞에서 includes를 왜 쓸까... 앞에서 left와 right의 인덱스일 경우까지는 바로 처리해줘도 무방하겠다. 하지만 코드는 다음과 같이 바뀌어야 한다.

function binarySearch(arr,val){
    let left = 0
    let right = arr.length-1
    let middle = Math.floor((left+right)/2)
    if(arr[left]==val) {
        return left
    } else if (arr[right] == val) {
        return right
    }
    while(arr[middle] != val && left <= right) {	
        if(arr[middle] > val) {
            right = middle - 1
        } else {
             left = middle + 1
        }
        middle = Math.floor((left+right)/2)
    }
    return left > right ? -1 : middle
}

앞부분에서 특수 케이스에 대한 처리를 한 후 (없어도 무방하다),
middle의 인덱스에 해당하는 배열의 값이 같거나 left가 right를 넘어서는 시점에 while이 끝나게 된다. 그리고 이후 left가 right보다 값이 큰지 검사해서 아니면 middle, 즉 인덱스 값을 반환하고 아니면 -1을 반환하게 된다.

값이 없는 경우에 left와 right가 교차하게 된다. 왜냐하면 중간값이 Math.floor일 경우엔 결국 중간값이 left로 설정되는 순간이 오게 되고, 이때 right가 middle-1, 즉 left-1로 설정되기 때문에 while을 빠져나오게 되고 Math.ceil일 경우엔 그 반대가 된다.

left와 right의 값은 같을 수 있다. left나 right의 값이 사실상 답인 인덱스였는데, 계속 줄여나거나 키우다보니 left = right = middle인 케이스도 존재하게 된다.

이를 통해 완벽한 이진탐색을 구현하였다.