정렬된 자연수로 이루어진 배열 'list' 중 특정 수 'num' 의 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개를 사용한다.
중간 값 ( mid )보다 찾고자하는 값이 크다면 left의 값은 mid + 1이 되고
중간 값 ( mid )보다 찾고자하는 값이 작다면 right의 값은 mid -1이 된다.
'51' 을 찾고 싶을 때 앞에서 수를 증가하면 5 step 이 필요하지만,
앞 뒤로 하나씩 수를 올리고 줄여가며 원하는 숫자를 찾는다면, 3 step 이면 가능하다.
선형 탐색으로 문제를 해결했을 때는 O(n) 이지만
이진 탐색을 쓰면 시간복잡도가 O(logn) 이 된다.
실제로 이진탐색을 사용하면 풀리는 문제가 코딩 테스트나 백준 및 프로그래머스와 같은 사이트에서 많이 나오고 있다.
소화화기 어려운 삶의 거대한 문제를 마주했을 때 순차적으로 문제를 해결하려 하지 말고 문제를 분류 후 하나씩 해결하다보면, 큰 문제를 효율적으로 해결하는 경우가 종종 있다. 이진 탐색을 통해 문제 해결에 대한 효율적인 접근 방식에 관해 더 치밀하게 고민해보자.
술자리에서 업다운 게임을 할 때만 이진 탐색을 하지 말고.