[자료구조] 이진탐색

#질문

 

임의의 수로 이루어진 배열 'list' 중 특정 수의 index를 찾아야 한다. 최적의 알고리즘은 무엇인가?

면접 때 받았던 질문이다. 이진 탐색을 알고 있어도 활용을 몰랐던 나는 아래와 같이 대답했다.

function solution(list, num) {
  return list.findIndex(x => x === num);
}

 

단순하게 받아들인 오답이었다.

 

# 풀이

 

면접관은 내게 이진 탐색에 관해 물어봤던 것이었다.
아래 코드는 위 코드와 같지만, 이진 탐색을 사용해 짠 코드이다.

 

function binarySearch(list, num) {
    let left = 0;
    let right = list.length-1;
    let mid = 0;

    while(left<=right){

        mid = parseInt((left+right)/2)

        if(num === list[mid]) {
            return mid;
        } else{
            if(num < list[mid]) {
                right = mid-1
            }
            else{
                left = mid+1
            }
        }
    }
}

 

변수는 총 3개를 사용한다.

• 최소 범위의 수를 뜻하는 left 변수(혹은 start)
• 최대 범위의 수를 뜻하는 right 변수(혹은 end)
• 특정 값이 담길 가운데 값 mid 변수

중간 값 ( mid )보다 찾고자하는 값이 크다면 left의 값은 mid + 1이 되고

중간 값 ( mid )보다 찾고자하는 값이 작다면 right의 값은 mid -1이 된다.

 

 

'51' 을 찾고 싶을 때 앞에서 수를 증가하면 5 step 이 필요하지만,
앞 뒤로 하나씩 수를 올리고 줄여가며 원하는 숫자를 찾는다면, 3 step 이면 가능하다.

 

내가 처음에 푼 것처럼 선형 탐색으로 문제를 해결했을 때는 O(n) 이지만
이진 탐색을 쓰면 시간복잡도가 O(logn) 이 된다.

 

실제로 이진탐색을 사용하면 풀리는 문제가 코딩 테스트나 백준 및 프로그래머스와 같은 사이트에서 많이 나오고 있다.

#마치며

소화화기 어려운 거대한 문제를 마주했을 때 순차적으로 문제를 해결하려 하지 말고 문제를 분류 후 하나씩 해결하다보면, 큰 문제를 효율적으로 해결하는 경우가 종종 있다. 이진 탐색처럼 문제 해결에 대한 효율적인 접근 방식에 관해 더 고민해보자.