탐색: 선형 탐색과 이진 탐색

정렬된 이름 100만 개 가운데 하나를 찾을 때, 이진 탐색은 20번 넘게 확인할 일이 없습니다.

값 하나 찾기

탐색은 모음 안에서 어떤 값이 어디 있는지 찾거나, 없다는 것을 알아내는 문제입니다. 휴대전화에 연락처 이름을 칠 때, 가게가 물건 재고를 확인할 때, 맞춤법 검사기가 낱말 하나하나를 확인할 때 탐색이 일어납니다. 입력은 목록과 찾을 값이고, 출력은 그 값의 위치이거나 「없음」을 뜻하는 -1 같은 표시입니다.

선형 탐색: 하나씩 차례로

가장 쉬운 방법은 왼쪽부터 값을 하나씩 확인하다가 찾는 값을 만나거나 목록이 끝나면 멈추는 것입니다. 이것이 선형 탐색입니다. 정렬되어 있든 아니든 어떤 목록에서나 쓸 수 있습니다. 드는 수고는 운에 달려 있습니다. 찾는 값이 맨 앞이면 한 번으로 끝나고, 맨 뒤에 있거나 아예 없으면 모든 값을 확인해야 합니다. 값이 n개면 최악의 경우 n번입니다. 목록 길이가 두 배면 확인도 두 배가 될 수 있어서, 일의 양이 크기에 따라 직선으로 늘어난다는 뜻으로 「선형」이라고 부릅니다.

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // found it
  }
  return -1;                             // checked everything
}

이진 탐색: 남은 범위를 반으로

목록이 정렬되어 있으면 훨씬 잘할 수 있습니다. 숫자 맞히기 놀이를 떠올려 보세요. 한 사람이 1부터 100 사이의 수를 정하고 「더 크다」 또는 「더 작다」로만 대답합니다. 요령 있는 사람은 먼저 50을 부릅니다. 대답이 무엇이든 가능성의 절반이 사라집니다. 다음에는 남은 범위의 가운데를 부르고, 이렇게 계속합니다. 이진 탐색은 정렬된 목록에서 바로 이 일을 합니다. 찾는 값이 아직 있을 수 있는 구간 양 끝에 lo와 hi라는 표시를 둡니다. 가운데 값을 확인해서 찾는 값이면 끝냅니다. 가운데 값이 찾는 값보다 작으면 그 왼쪽은 모두 더 작으므로 lo를 가운데 다음 칸으로 옮깁니다. 크면 hi를 가운데 앞 칸으로 옮깁니다. lo가 hi를 넘어서면 남은 칸이 없으니 목록에 그 값이 없는 것입니다.

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // target is to the right
    else hi = mid - 1;                     // target is to the left
  }
  return -1;
}

몇 번 확인할까요?

이진 탐색은 한 번 확인할 때마다 남은 구간을 적어도 절반으로 줄입니다. 값 n개에서 시작하면 한 번 뒤에는 많아야 약 n/2개, 두 번 뒤에는 약 n/4개가 남고, 이렇게 하나가 남을 때까지 갑니다. n을 1까지 줄이는 데 필요한 반 가르기 횟수를 밑이 2인 로그라고 하고 log₂ n으로 씁니다. 마지막 확인까지 세면 이진 탐색은 많아야 ⌊log₂ n⌋ + 1번 확인합니다. ⌊ ⌋는 내림을 뜻합니다. 값 100개라면 7번이어서, 숫자 맞히기 놀이는 언제나 7번 안에 이길 수 있습니다. 1,000개면 10번, 100만 개면 20번, 10억 개면 30번입니다.

조건: 목록이 정렬되어 있어야 합니다

이진 탐색이 통하는 까닭은 정렬된 목록에서는 비교 한 번으로 찾는 값이 어느 쪽에 있어야 하는지 알 수 있기 때문입니다. 정렬되지 않은 목록에서는 가운데 값이 이웃에 대해 아무것도 알려 주지 않으므로 다시 선형 탐색으로 돌아가야 합니다. 정렬 자체에도 수고가 들기 때문에(다음 두 단원의 주제입니다) 어떻게 쓰느냐에 따라 고릅니다. 목록을 한 번만 찾는다면 선형 탐색이 가장 쌀 수 있습니다. 같은 목록을 수천 번 찾는다면 한 번 정렬해 두고 이진 탐색을 쓰는 편이 금방 이득입니다. 데이터를 준비하는 수고와 질문에 답하는 수고를 맞바꾸는 일은 이 분야 전체에 걸쳐 나옵니다.