선형 탐색과 이진 탐색, 언제 어느 쪽이 유리한가

김데브 · 게시 2026.07.20 · 약 7분 분량

선형 탐색은 데이터를 앞에서부터 하나씩 확인하는 방식이고, 이진 탐색은 정렬된 데이터의 가운데 값과 비교해 찾을 범위를 절반씩 줄이는 방식이다. 원소가 n개일 때 선형 탐색은 최악의 경우 n번을 비교하지만(O(n)), 이진 탐색은 약 log₂n번이면 끝난다(O(log n)). 대신 데이터가 미리 정렬돼 있어야 한다. 그래서 실무 선택은 단순하다. 데이터가 작거나 정렬돼 있지 않거나 한 번만 찾는다면 선형 탐색, 크고 이미 정렬된 데이터를 여러 번 뒤진다면 이진 탐색이다.

이 글은 배열이나 리스트처럼 순서대로 놓인 자료구조에서의 두 탐색을 다룬다. 근거는 파이썬 공식 문서의 bisect 모듈과 구글 리서치 블로그에 실린 이진 탐색 오버플로 사례에서 가져왔다. 해시 테이블이나 트리 기반 조회는 비교 대상으로만 짚고 깊게 파고들지 않는다.

선형 탐색과 이진 탐색의 작동 방식

선형 탐색(linear search)은 리스트의 첫 원소부터 순서대로 목표 값과 비교한다. 찾으면 그 위치를 돌려주고, 끝까지 없으면 실패로 끝낸다. 정렬 여부와 상관없이 어떤 배열에도 그대로 얹을 수 있다는 게 장점이다. 대신 원소가 100만 개면 목표가 맨 뒤에 있거나 아예 없을 때 100만 번을 비교한다.

이진 탐색(binary search)은 정렬된 배열에서만 통한다. 가운데 원소를 목표와 비교해서, 목표가 더 크면 왼쪽 절반을 통째로 버리고 오른쪽 절반만 같은 방식으로 다시 뒤진다. 한 번 비교할 때마다 남은 후보가 절반으로 줄기 때문에, 100만 개짜리 배열도 스무 번 안쪽이면 결판이 난다. log₂(1,000,000)이 약 19.9라서 최악에도 20번이면 충분하다.

핵심 차이는 “가운데와 비교해 절반을 버린다”는 전략이 정렬을 전제로 한다는 점이다. 순서가 깨져 있으면 버린 절반에 목표가 숨어 있을 수 있어서, 이진 탐색은 태연하게 틀린 답을 내놓는다. 이 한 줄이 두 알고리즘의 성격과 쓰임새를 전부 가른다.

시간 복잡도로 보는 성능 차이

두 탐색의 성격은 시간 복잡도로 정리하면 한눈에 들어온다.

표에서 가장 중요한 칸은 최악 복잡도다. 선형 탐색은 평균이든 최악이든 O(n)이라 원소 수에 정비례해 느려진다. 이진 탐색은 절반씩 줄이니 O(log n)이고, 원소가 열 배로 늘어도 비교 횟수는 서너 번밖에 더 늘지 않는다. 로그 함수가 얼마나 완만하게 자라는지를 실제 숫자로 보면 감이 온다.

원소가 10억 개로 불어나도 이진 탐색은 서른 번이면 끝나지만, 선형 탐색은 10억 번을 각오해야 한다. 이 격차가 정렬 비용을 감수하면서까지 이진 탐색을 쓰는 이유의 거의 전부다.

이진 탐색은 왜 정렬을 전제로 하나

이진 탐색이 정렬을 요구하는 건 “가운데보다 크면 오른쪽, 작으면 왼쪽”이라는 판단이 정렬된 상태에서만 참이기 때문이다. 데이터가 뒤섞여 있으면 절반을 버리는 근거 자체가 무너진다.

문제는 정렬이 공짜가 아니라는 데 있다. 비교 기반 정렬은 일반적으로 O(n log n)이 든다. 정렬 안 된 데이터를 딱 한 번 찾겠다고 정렬부터 하면, 정렬 비용 O(n log n)이 선형 탐색 한 번 O(n)보다 오히려 비싸다. 한 번 쓰고 버릴 데이터라면 그냥 처음부터 훑는 편이 이득이다.

이진 탐색이 본전을 뽑는 건 한 번 정렬해 둔 데이터를 반복해서 조회할 때다. 조회를 m번 한다고 치면 선형은 m×O(n)이고, 정렬 후 이진은 O(n log n) + m×O(log n)이다. m이 커질수록 뒤쪽 식이 압도적으로 싸진다. 그래서 판단 기준은 간단하다. 같은 데이터를 앞으로 몇 번이고 다시 찾을 거라면 정렬해 두고 이진 탐색, 한두 번 훑고 버릴 거라면 선형 탐색이다.

코드로 확인하는 두 탐색

파이썬으로 두 탐색을 직접 짜 보면 구조 차이가 분명하다. 먼저 선형 탐색은 반복문 하나가 전부다.

def linear_search(arr, target):
  for i, value in enumerate(arr):
    if value == target:
      return i
  return -1

이진 탐색은 low와 high로 남은 구간을 좁혀 간다. 가운데를 확인하고, 목표가 크면 low를 올리고 작으면 high를 내린다.

def binary_search(arr, target):
  low, high = 0, len(arr) - 1
  while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
      return mid
    elif arr[mid] < target:
      low = mid + 1
    else:
      high = mid - 1
  return -1

실무에서는 이걸 직접 짜기보다 표준 라이브러리를 쓴다. 파이썬 공식 문서의 bisect 모듈은 정렬된 리스트에 대한 이진 탐색을 bisect_left와 bisect_right로 제공한다. 파이썬 공식 문서에 따르면 bisect_left는 같은 값이 여러 개일 때 가장 왼쪽 삽입 위치를, bisect_right는 가장 오른쪽 다음 위치를 돌려준다.

import bisect

data = [1, 3, 4, 4, 7, 9]
bisect.bisect_left(data, 4)  # 2 (같은 값 중 가장 왼쪽)
bisect.bisect_right(data, 4) # 4 (가장 오른쪽 다음)

값이 있는지만 알고 싶은 게 아니라 “정렬을 유지하며 어디에 끼워 넣어야 하는지”까지 한 번에 얻을 수 있어서, 정렬된 데이터를 다룰 때 손으로 짠 이진 탐색보다 실수가 적다.

이진 탐색을 직접 짤 때 흔한 함정

이진 탐색은 개념은 단순한데 손으로 짜면 유난히 버그가 잦다. 가장 유명한 사례가 가운데 값을 구하는 한 줄이다. 구글 리서치 블로그에 2006년 조슈아 블로크(Joshua Bloch)가 올린 글에 따르면, 자바 표준 라이브러리의 java.util.Arrays.binarySearch를 포함한 대다수 이진 탐색 구현에 정수 오버플로 버그가 약 9년간 숨어 있었다. 문제의 코드는 (low + high) / 2다. low와 high를 먼저 더하는데, 그 합이 int 최대값(2³¹-1)을 넘으면 음수로 뒤집히고, 잘못된 가운데 값이 나온다.

같은 블로그 글에 따르면 이 버그는 배열 원소가 약 2³⁰개(약 10억 개) 이상일 때 드러난다. 1980년대 프로그래밍 펄스(Programming Pearls)의 원본 구현부터 이어져 온 문제라, 당시엔 상상하기 힘든 규모였지만 지금은 흔하다. 해법은 두 값을 그대로 더하지 않는 것이다.

// 오버플로 위험: low + high가 int 최대값을 넘으면 음수가 된다
int mid = (low + high) / 2;

// 안전: high - low는 음수가 될 수 없어 넘치지 않는다
int mid = low + (high - low) / 2;

// JDK가 실제로 쓰는 방식 (부호 없는 오른쪽 시프트)
int mid = (low + high) >>> 1;

참고로 파이썬은 정수 크기에 상한이 없어서 (low + high) // 2가 넘칠 일이 없다. 이 오버플로는 자바나 C, C++, 고(Go)처럼 고정 폭 정수를 쓰는 언어에서만 신경 쓰면 된다.

오버플로 말고도 함정은 더 있다. 반복 조건을 low < high로 쓸지 low <= high로 쓸지, 범위를 좁힐 때 mid를 포함할지 mid에서 한 칸 건너뛸지에 따라 목표를 놓치거나 무한 루프에 빠진다. 경계 조건은 원소 0개·1개·2개짜리 배열로 반드시 검증하는 편이 안전하다.

실무에서 어느 쪽을 고를까

결론부터 말하면, 정렬된 데이터를 반복 조회할 때는 직접 짜지 말고 언어가 주는 이진 탐색 함수를 먼저 쓴다. 자바는 Arrays.binarySearch와 Collections.binarySearch, 파이썬은 bisect, C++은 std::lower_bound와 std::binary_search를 표준으로 제공한다. 자바 표준 라이브러리의 Arrays.binarySearch는 값을 찾으면 인덱스를, 못 찾으면 -(삽입 위치)-1을 돌려준다. 이 음수 반환값을 그대로 삽입 위치 계산에 쓸 수 있어 편하다.

선형 탐색이 더 나은 경우도 분명하다. 원소가 수십 개 안팎으로 적으면 복잡도 차이가 체감되지 않고, 오히려 분기 없는 순차 접근이 CPU 캐시(자주 쓰는 데이터를 프로세서 가까이 미리 담아 두는 저장 공간)에 유리하다. 데이터가 정렬돼 있지 않고 한 번만 찾을 거라면 정렬 비용이 아까우니 선형이 맞다. 매번 새로 들어오는 스트림처럼 정렬 상태를 유지하기 어려운 데이터도 마찬가지다.

한 가지 더. 단순히 값이 있는지 없는지만 판단하는 멤버십 검사라면, 정렬 후 이진 탐색보다 해시 셋(평균 O(1))이 대개 낫다. 값이 정확히 일치하는지가 아니라 의미가 비슷한 벡터를 찾는 문제라면 선형·이진 탐색의 영역이 아니라 근사 최근접 이웃 인덱스가 필요한데, 이때는 벡터 검색 인덱스를 다루는 별도의 접근으로 넘어가야 한다. 선형과 이진 탐색은 ‘정렬된 배열에서 정확한 값 찾기’라는 좁고 흔한 문제에서 여전히 가장 먼저 꺼내는 기본 도구다.