Big O로 이해하는 배열과 탐색의 원리

번호가 붙은 사물함 100개를 떠올려 보자. “3번 사물함을 열어 주세요”라는 요청은 바로 처리할 수 있다. 반면 “빨간 가방이 든 사물함을 찾아 주세요”라는 요청은 가방의 위치를 모르면 여러 사물함을 열어 봐야 한다.

배열에서도 위치를 알고 값을 꺼내는 일과 값이 있는 위치를 찾는 일은 다르다. 이 차이를 설명하는 도구가 시간 복잡도와 Big O다.

먼저 구분하기: 선형 탐색과 이진 탐색

탐색은 원하는 값이 있는지, 어디에 있는지 찾는 작업이다. 이 글에서는 두 가지 방법을 비교한다.

구분	선형 탐색	이진 탐색
찾는 방법	앞에서부터 하나씩 확인한다	가운데 값과 비교해 후보 범위를 절반씩 줄인다
정렬 필요 여부	정렬되지 않아도 사용할 수 있다	작은 값부터 큰 값 순서처럼 일정한 기준으로 정렬되어 있어야 한다

선형 탐색은 하나씩 확인하고, 이진 탐색은 정렬 정보를 이용해 여러 후보를 한꺼번에 제외한다. 구체적인 과정은 4장과 5장에서 살펴본다.

배열의 접근과 탐색 비용을 이해하려면 다음 질문을 살펴볼 필요가 있다.

• 같은 배열을 사용하는데 왜 접근과 탐색의 비용이 다를까?
• 배열 앞에 추가하는 것과 끝에 추가하는 것은 무엇이 다를까?
• 이진 탐색은 왜 정렬된 데이터에서 사용할 수 있을까?
• 탐색 범위를 절반으로 줄이면 왜 로그가 나올까?

Big O의 의미부터 살펴보고, 각 연산이 어떤 정보를 알고 시작하며 어떤 작업을 수행하는지를 따라가 보자.

용어가 낯설다면: 배열·원소·인덱스·n

용어	이 글에서의 의미	예시
알고리즘	문제를 해결하는 작업 순서	앞에서부터 하나씩 확인하기
배열	여러 값을 순서대로 담은 자료구조	[10, 20, 30]
원소	배열에 들어 있는 값 하나	위 배열의 20
인덱스	원소의 위치를 나타내는 번호. 0부터 센다	20의 인덱스는 1
탐색	원하는 값이 있는지, 어디에 있는지 찾는 작업	배열에서 20 찾기
n	처리할 데이터의 개수	위 배열에서는 n = 3

읽는 순서

처음에는 본문과 그림을 따라가고, 코드·수식·추가 예시가 필요할 때 토글을 펼쳐 보자. 코드는 JavaScript로 작성했다.

---

1. 시간 복잡도와 Big O

시간보다 연산량을 분석하는 이유

알고리즘의 성능을 비교하는 가장 직접적인 방법은 실행 시간을 측정하는 것이다.

하지만 같은 코드라도 실행 환경에 따라 결과가 달라진다. CPU 성능, 메모리 상태, JavaScript 엔진의 최적화 등이 실행 시간에 영향을 주기 때문이다.

시간 복잡도는 이러한 차이를 잠시 제외하고 다음 질문에 집중한다.

입력 크기가 커지면 처리해야 할 작업은 얼마나 증가하는가?

배열의 합계를 구하려면 모든 값을 한 번씩 더해야 한다. 값이 3개면 3번, 100개면 100번 더한다. 이렇게 데이터 개수에 비례해 작업량이 늘어나는 경우를 O(n)으로 표현한다.

코드와 수식으로 확인하기: 배열의 합계

예를 들어 배열의 합계를 구하는 함수를 살펴보자.

function sum(numbers) {
  let total = 0;

  for (let i = 0; i < numbers.length; i++) {
    total += numbers[i];
  }

  return total;
}

이 함수는 배열의 값을 앞에서부터 하나씩 꺼내 total에 더한 뒤 합계를 돌려준다. [10, 20, 30]을 넣으면 10 + 20 + 30을 계산해 60을 돌려준다.

배열의 길이를 n이라고 하면 덧셈은 n번 실행된다.

실제로는 덧셈뿐 아니라 인덱스 증가, 반복 조건 확인, 원소 접근도 발생한다. 각 작업을 일정한 비용으로 가정하면 전체 연산량을 다음과 같이 표현할 수 있다.

T(n) = an + b

• a: 반복 한 번에서 수행하는 작업의 비용
• b: 초기화, 반환 등 반복 횟수와 무관한 비용

T(n)은 “데이터가 n개일 때의 전체 작업량”이라는 이름이다. an은 a × n을 뜻한다.

a, b의 정확한 값이 달라도 입력 크기에 비례해 작업량이 증가한다는 특징은 유지된다.

O(1), O(n), O(log n)을 먼저 말로 읽어 보기

O는 숫자 0이 아니라 알파벳 O이며, “빅 오”라고 읽는다. 괄호 안에는 데이터가 늘 때 작업량이 커지는 방식을 적는다.

표기	말로 풀면	대표 예시
O(1)	데이터가 늘어도 작업량이 일정한 범위에 머문다	알고 있는 인덱스의 값 읽기
O(n)	데이터 개수에 비례하는 수준으로 작업량이 늘어난다	모든 원소를 한 번씩 확인하기
O(log n)	후보를 계속 절반으로 줄여 작업량이 천천히 늘어난다	정렬된 배열에서 이진 탐색하기
O(n²)	데이터 개수의 제곱에 비례하는 수준으로 작업량이 늘어난다	각 원소마다 모든 원소를 다시 확인하기

O(1)이 “정확히 한 번 실행한다”거나 “1초 걸린다”는 뜻은 아니다. 3번의 계산이 필요해도 데이터 개수와 무관하게 일정하다면 O(1)이다. 로그는 뒤에서 숫자 예시로 살펴본다.

위 표는 각 작업의 증가율을 가깝게 나타내는 표기를 사용한 것이다. 엄밀히 Big O는 충분히 큰 입력에서 작업량이 넘지 않는 기준인 상한을 표현한다.

더 알아보기: Big O의 수학적 정의

Big O는 함수의 점근적 상한을 나타낸다.

여기서 “점근적”은 데이터가 충분히 커졌을 때를 본다는 뜻이고, “상한”은 작업량이 넘지 않는 기준을 뜻한다.

쉽게 풀면 다음과 같다.

입력이 충분히 커진 이후에는, 연산량이 어떤 기준 함수의 상수 배수를 넘지 않는다는 의미다.

수식으로는 다음과 같이 표현한다.

T(n) ≤ c · f(n)    (n ≥ n₀)

이를 만족하는 양의 상수 c와 기준 크기 n₀가 존재하면 T(n) = O(f(n))이라고 한다.

f(n)은 비교 기준이 되는 함수이고, c는 그 기준에 곱하는 고정된 수다. n₀는 이 비교가 성립하기 시작하는 데이터 개수다. ≤는 “작거나 같다”, ≥는 “크거나 같다”로 읽는다.

예를 들어 다음 함수가 있다고 하자.

T(n) = 3n + 10

n ≥ 10이면 다음 관계가 성립한다.

3n + 10 ≤ 4n

따라서 T(n)은 O(n)이다.

엄밀히는 3n + 10을 O(n²)이라고 해도 상한이라는 정의에는 맞는다. 다만 너무 느슨한 설명이므로, 보통은 증가율을 더 가깝게 나타내는 O(n)을 사용한다.

왜 3n + 10에서 n만 남길까?

다음 두 연산량을 비교해 보자.

A: 3n + 10
B: n² + 2n + 1

A는 입력이 두 배가 되면 주된 연산량도 약 두 배가 된다.

B는 입력이 두 배가 되면 가장 큰 영향을 주는 n² 항이 네 배가 된다. 입력이 커질수록 2n + 1보다 n²의 영향이 커진다.

n²은 n × n이다. 예를 들어 n = 100이면 n²은 10,000이고, 2n + 1은 201이다. 데이터가 클수록 제곱 부분이 전체 작업량을 좌우한다.

따라서 증가율을 비교할 때는 다음처럼 정리한다.

3n + 10       → O(n)
n² + 2n + 1   → O(n²)

상수와 낮은 차수의 항이 실제 실행 시간에 영향을 주지 않는다는 뜻은 아니다. 입력이 커질 때 지배적인 증가율을 보기 위해 생략하는 것이다.

그래서 작은 데이터에서는 O(n²) 알고리즘이 어떤 O(n) 알고리즘보다 빠를 수도 있다. Big O는 모든 입력 크기에서의 속도 순위를 보장하지 않는다.

Big O와 최악의 경우는 별개다

배열을 앞에서부터 탐색하면 찾는 값의 위치에 따라 작업량이 달라진다.

• 첫 번째에 있다면 한 번만 확인한다.
• 찾는 값이 마지막에만 있다면 전체를 확인한다.
• 존재하지 않는다면 역시 전체를 확인한다.

여기서 먼저 결정해야 하는 것은 어떤 상황의 비용을 분석할 것인지다.

분석 대상	의미	선형 탐색의 예
최선	가장 적은 작업이 필요한 입력	첫 번째에서 발견
최악	가장 많은 작업이 필요한 입력	끝에서 처음 발견하거나 없음
평균	각 상황이 일어날 확률을 고려한 평균 작업량	각 위치에 같은 확률로 존재한다고 가정

각 상황의 연산량을 Big O로 표현할 수 있다.

따라서 Big O 자체가 최악의 경우를 의미하지는 않는다. “선형 탐색의 최악 시간 복잡도는 O(n)이다”처럼 분석 대상과 표기법을 구분해야 한다.

---

2. 배열의 인덱스 접근이 빠른 이유

전통적인 배열의 메모리 구조

전통적인 배열은 같은 크기의 원소가 연속된 메모리 공간에 저장되는 구조다.

메모리는 프로그램이 값을 저장하는 공간이고, 주소는 그 공간의 위치 번호다. 같은 크기의 사물함이 빈틈없이 나란히 놓여 있다고 생각하면 된다. 바이트는 저장 공간의 크기를 세는 단위다.

숫자로 확인하기: 인덱스로 메모리 주소 계산

다음 조건을 가정해 보자.

• 배열의 시작 주소: 1000
• 원소 하나의 크기: 4바이트
• 인덱스는 0부터 시작

인덱스	원소의 시작 주소
0	1000
1	1004
2	1008
3	1012

특정 원소의 주소는 다음 공식으로 계산할 수 있다.

원소 주소 = 배열 시작 주소 + 인덱스 × 원소 크기

예를 들어 인덱스 3에 접근한다면 다음과 같다.

1000 + 3 × 4 = 1012

배열의 시작 주소와 원소 크기를 알면, 인덱스로 원하는 위치의 주소를 바로 계산할 수 있다. 앞의 원소를 하나씩 방문할 필요가 없다.

배열에 원소가 10개 있든 100만 개 있든 주소 계산에 필요한 작업 수는 일정하다. 일반적인 계산 모델에서 인덱스 접근을 O(1)로 분석하는 이유다.

배열의 빠른 접근은 “어느 위치를 읽을지 이미 알고 있다”는 전제에서 나온다.

값으로 탐색하면 왜 달라질까?

const numbers = [40, 10, 70, 20];

numbers[2];          // 인덱스를 알고 접근
numbers.indexOf(70);  // 값을 바탕으로 위치를 찾음

인덱스를 알고 있다면 해당 위치에 접근하면 된다.

하지만 값 70만 알고 있을 때는 주소 계산에 필요한 인덱스 자체를 모른다.

정렬이나 별도의 조회 구조가 없다면 값을 차례대로 비교해야 한다.

배열에서 “조회가 빠르다”라고 설명할 때는 이 둘을 구분해야 한다.

이후 설명의 전제

JavaScript 배열의 실제 저장 방식은 엔진과 배열 상태에 따라 달라진다. 이후에는 빈칸 없이 값이 채워진 배열과, 필요할 때 저장 공간을 늘리는 동적 배열 모델로 원리를 설명한다.

더 알아보기: JavaScript 배열의 실제 저장 방식

JavaScript의 Array는 전통적인 고정 크기 배열과 동일한 구현을 보장하지 않는다.

const values = [1, "hello", { id: 1 }];

서로 다른 종류의 값을 담을 수 있고, 길이가 바뀔 수 있으며, 중간에 빈 슬롯도 생길 수 있다.

엔진은 이러한 특성을 지원하면서 성능을 높이기 위해 여러 내부 표현을 사용한다. V8은 원소의 종류나 빈 슬롯 유무 등을 구분하여 최적화한다. (V8 — Elements kinds)

앞의 연속 저장 설명은 자료구조의 원리를 이해하기 위한 모델이며, 모든 JavaScript 배열의 내부 구조를 그대로 묘사한 것은 아니다.

---

3. 배열의 삽입·삭제 비용이 달라지는 이유

앞에 추가하면 기존 위치가 바뀐다

다음 배열의 앞에 5를 추가한다고 하자.

const numbers = [10, 20, 30];

numbers.unshift(5);

새 값을 넣는 작업만 필요한 것이 아니다. 기존 원소가 뒤쪽 인덱스에 위치하도록 처리해야 한다.

일반적인 배열 모델에서는 원소 n개를 이동해야 하므로 O(n)이다.

앞에서 삭제할 때도 같은 원리

앞에서 원소를 제거하는 shift()도 같은 원리다. 첫 원소를 제거한 뒤 남은 원소의 인덱스를 하나씩 줄여야 한다. ECMAScript 명세 역시 뒤쪽 인덱스를 순서대로 처리하는 절차로 이를 정의하지만, 실제 엔진은 최적화를 적용할 수 있다. (ECMAScript — Array.prototype.shift)

중간 삽입은 위치에 따라 이동량이 달라진다

예시: 중간에 넣을 때 몇 개를 옮길까?

길이가 n인 배열의 인덱스 i에 원소를 하나 추가한다면, 일반적인 배열 모델에서 이동 대상은 뒤쪽의 n - i개 원소다.

예를 들어 [10, 20, 30, 40]의 인덱스 2에 25를 넣으려면, 30과 40을 한 칸씩 뒤로 옮겨야 한다. 이때 n = 4, i = 2이므로 옮기는 원소는 4 - 2 = 2개다.

앞에 삽입: n개 이동
중간에 삽입: 뒤쪽 원소 이동
끝에 삽입: 인덱스를 바꾸기 위한 이동 없음 (공간 확장 비용은 별도)

따라서 배열의 삽입 비용을 설명할 때는 어디에 삽입하는지가 중요하다.

끝에 추가하는 push()가 일반적으로 효율적인 이유도 기존 원소의 순서와 인덱스를 변경할 필요가 없기 때문이다.

그런데 push()는 왜 항상 O(1)이라고 하지 않을까?

동적 배열 모델에서는 두 가지를 구분한다.

• 길이(length): 현재 저장된 원소 수
• 용량(capacity): 현재 저장 공간이 수용할 수 있는 원소 수

예를 들어 길이가 3이고 용량이 4라면 한 개를 추가할 여유가 있다.

칸이 4개인 상자에 물건 3개를 담아 둔 것과 같다. 이 용량은 엔진 내부의 저장 공간을 설명하는 개념이며 JavaScript 배열의 .length와는 다르다.

하지만 길이와 용량이 모두 4인 상태에서 추가한다면 더 큰 저장 공간이 필요할 수 있다. 이때 기존 원소를 복사하는 비용이 발생한다.

따라서 개별 push()의 비용은 다음처럼 달라질 수 있다.

상황	작업	비용
여유 공간 있음	끝에 원소 추가	O(1)
공간 확장 필요	기존 원소 복사 후 추가	O(n)

이 설명은 동적 배열 모델에 대한 것이며, JavaScript 엔진이 반드시 같은 확장 정책을 사용한다는 의미는 아니다.

여러 번 추가한 전체 비용은?

용량을 일정 비율로 늘리는 동적 배열에서는 여러 번 추가한 전체 비용을 나누면 추가 1회당 **분할 상환 O(1)**이다. 개별 추가가 항상 빠르다는 뜻은 아니다.

심화: 분할 상환 O(1)을 계산하는 과정과 그림

초기 용량이 1인 빈 배열에서 시작해, 공간이 부족할 때 용량을 두 배씩 확장한다고 가정해 보자.

1 → 2 → 4 → 8 → 16 → …

확장할 때 복사하는 원소 수는 다음처럼 늘어난다.

1 + 2 + 4 + 8 + …

빈 배열에 총 n개의 원소를 추가하는 동안, 이 복사 횟수의 합은 2n보다 작게 제한할 수 있다.

예를 들어 처음 용량이 1인 빈 배열에 원소 8개를 차례로 넣으면, 용량을 2, 4, 8로 늘릴 때 각각 1개, 2개, 4개를 복사한다. 복사는 총 7번이고, 새 값을 쓰는 8번까지 합치면 15번이다. 8번의 추가에 비용을 나누면 한 번당 2번 미만의 작업인 셈이다. 여기서는 복사와 새 값 쓰기를 각각 한 번의 작업으로 센다.

새 원소를 쓰는 작업 n번까지 포함해도 전체 비용은 O(n)이다.

n번 추가하는 전체 비용: O(n)
추가 1회당 나눈 비용: O(1)

평균 시간 복잡도와는 다르다. 입력이 어떤 확률로 등장하는지 가정하는 대신, 비싼 연산을 포함한 전체 연산 순서의 비용을 계산한다.

---

4. 선형 탐색이 최악 O(n)인 이유

확인하지 않은 위치에 답이 있을 수 있다

정렬되지 않은 배열에서 특정 값을 찾는다고 하자.

const numbers = [30, 10, 50, 20];

첫 번째 값 30이 찾는 값과 다르다는 사실만으로는 나머지 원소에 대해 알 수 있는 것이 없다.

• 두 번째에 있을 수도 있다.
• 마지막에 있을 수도 있다.
• 아예 없을 수도 있다.

확인하지 않은 위치를 안전하게 제외할 근거가 없으므로 하나씩 검사해야 한다.

이것이 선형 탐색의 기본 원리다.

코드 보기: 선형 탐색

target은 찾으려는 값이다. 아래 함수는 값을 찾으면 그 위치의 인덱스를 돌려주고, 끝까지 없으면 -1을 돌려준다. 인덱스는 0부터 시작하므로 -1을 “찾지 못함”의 표시로 쓸 수 있다.

function linearSearch(numbers, target) {
  for (let index = 0; index < numbers.length; index++) {
    if (numbers[index] === target) {
      return index;
    }
  }

  return -1;
}

찾는 값이 첫 번째에 있다면 한 번의 비교로 끝난다.

반대로 찾는 값이 마지막에만 있거나 존재하지 않으면 n개를 모두 비교한다.

따라서 다음과 같이 분석한다.

• 최선 시간 복잡도: O(1)
• 최악 시간 복잡도: O(n)
• 추가 공간 복잡도: O(1)

추가 공간이란?

추가 공간 복잡도는 작업 중 별도로 필요한 저장 공간이 데이터 개수에 따라 얼마나 늘어나는지 나타낸다. 추가 공간이 O(1)인 이유는 배열 크기가 커져도 인덱스 등 일정한 개수의 변수만 사용하기 때문이다. 입력 배열 자체의 저장 공간은 여기서 제외한다.

더 알아보기: 평균적으로 절반만 확인해도 O(n)인 이유

찾는 값이 배열에 정확히 한 번 존재하고, 각 위치에 있을 확률이 같다고 가정하자.

필요한 비교 횟수는 위치에 따라 1, 2, …, n번이다.

먼저 원소가 4개라면, 찾는 위치에 따라 1번, 2번, 3번, 4번 비교한다. 네 위치가 똑같이 가능하다고 가정했으므로 평균은 (1 + 2 + 3 + 4) / 4 = 2.5번이다. 이 계산을 n개로 확장하면 다음 식이 된다.

(1 + 2 + ⋯ + n) / n
= n(n + 1) / (2n)
= (n + 1) / 2

평균적으로 약 절반을 확인하지만, 입력이 두 배가 되면 평균 작업량도 대략 두 배가 된다.

상수 배수를 제외하면 평균 시간 복잡도 역시 O(n)이다.

find()도 같은 방식일까?

find()는 배열에 붙어 있는 탐색 기능(메서드)이다. 조건을 만족하는 첫 번째 원소의 값을 돌려주며, 없으면 undefined를 반환한다. 앞의 linearSearch()가 위치를 반환하는 것과는 다르다.

검사할 함수인 콜백을 전달하며, 아래 코드의 검사 조건은 user.id === targetId다.

const user = users.find((user) => user.id === targetId);

find()는 인덱스 순서대로 콜백을 실행하다가 조건을 만족하면 종료한다. 정렬된 배열이라고 해서 자동으로 이진 탐색으로 바뀌지는 않는다. (MDN — Array.prototype.find())

응용: find() 안에서 includes()를 호출하면?

전체 비용에는 콜백 내부에서 수행하는 작업도 포함해야 한다.

const user = users.find((user) =>
  selectedIds.includes(user.id),
);

사용자가 n명이고 선택된 ID가 m개라면, 최악에는 사용자마다 ID를 m개씩 확인한다. 여기서는 m이 1 이상이고 ID 한 번의 비교 비용이 O(1)이라고 가정한다.

includes()는 배열에 해당 값이 있는지 검사한다. 사용자가 100명이고 선택된 ID가 20개이며 일치하는 ID가 없다면, 최대 100 × 20 = 2,000번의 ID 비교가 필요하다. nm은 이처럼 n × m을 뜻한다.

최악의 전체 비용: O(nm)

배열 메서드의 복잡도는 몇 번 호출하는지와 호출 한 번이 얼마나 비싼지를 함께 계산해야 한다.

---

5. 이진 탐색이 가능한 이유

정렬은 확인하지 않은 값에 대한 정보를 제공한다

작은 값부터 큰 값 순서인 오름차순으로 정렬된 배열을 보자.

const numbers = [10, 20, 30, 40, 50, 60, 70];

가운데 원소의 값은 40이다.

정렬되어 있으므로 다음 사실을 알 수 있다.

• 중앙보다 왼쪽에 있는 값은 모두 40 이하이다.
• 중앙보다 오른쪽에 있는 값은 모두 40 이상이다.

찾는 값이 60이라면 왼쪽 원소를 각각 확인하지 않아도 된다. 왼쪽에는 40보다 큰 값이 없기 때문이다.

이진 탐색은 정렬 정보를 이용해, 확인하지 않은 원소들을 후보에서 한꺼번에 제외한다.

정렬되지 않았다면 가운데 원소의 값이 40이어도 왼쪽에 60이 있을 수 있다. 범위 절반을 제외할 근거가 사라진다.

아래 그림에서는 40을 확인한 뒤 남은 [50, 60, 70]에서 60을 확인한다. 선형 탐색은 원소를 6번, 이진 탐색은 2번 확인해 찾는다.

코드 보기: 이진 탐색과 변수 설명

다음 코드는 배열과 찾는 값이 정상적으로 크기 비교 가능한 숫자라고 가정한다. NaN은 “숫자가 아님”을 나타내는 특수 값으로, 여기서는 제외한다. 배열은 미리 오름차순으로 정렬되어 있어야 한다.

function binarySearch(numbers, target) {
  let left = 0;
  let right = numbers.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const value = numbers[mid];

    if (value === target) {
      return mid;
    }

    if (value < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

각 변수의 의미는 다음과 같다.

변수	의미
left	아직 후보로 남아 있는 구간의 시작 인덱스
right	아직 후보로 남아 있는 구간의 마지막 인덱스
mid	이번에 확인할 중앙 인덱스

Math.floor()는 주어진 수 이하의 가장 큰 정수로 내림한다. 여기서는 0 이상의 거리를 계산하므로 소수점 부분을 버리는 것과 같다. 예를 들어 left = 0, right = 5이면 중앙 인덱스를 2로 잡는다. 원소가 짝수 개일 때는 가운데 두 위치 중 왼쪽을 고른다. (ECMAScript — Math.floor)

return mid는 찾은 위치를 돌려주며 함수를 끝내고, return -1은 찾지 못했다는 뜻이다. 같은 값이 여러 개면 그중 하나의 위치를 반환하며, 반드시 첫 번째 위치를 반환하지는 않는다.

심화: 정답 후보를 버리지 않는 이유 — 루프 불변식

이 코드가 올바르려면 다음 조건을 유지해야 한다.

찾는 값이 존재한다면, 현재의 [left, right] 구간 안에 있다.

반복 전후에 유지되는 이러한 조건을 루프 불변식이라고 한다. 이진 탐색에서는 범위를 줄여도 정답 후보를 버리지 않았다는 근거가 된다. (Cornell University — Loop invariants)

• 시작: 배열 전체를 후보로 두므로, 찾는 값이 있다면 구간 안에 있다.
• 오른쪽만 남길 때: 가운데 값이 찾는 값보다 작으면, 그 값과 왼쪽 값들은 모두 정답이 아니다. left = mid + 1로 제외해도 정답 후보는 남는다.
• 왼쪽만 남길 때: 가운데 값이 찾는 값보다 크면, 그 값과 오른쪽 값들은 모두 정답이 아니다. right = mid - 1로 제외할 수 있다.
• 종료: 값을 찾으면 위치를 반환한다. 찾지 못한 채 left > right가 되면 후보가 없으므로 -1을 반환한다.

구현 주의점: 경계의 +1, -1과 반복 조건

가운데 값이 찾는 값과 다르다면 해당 위치도 다음 후보에서 제외해야 한다. 그래서 오른쪽으로 갈 때는 left = mid + 1, 왼쪽으로 갈 때는 right = mid - 1로 갱신한다.

위 구현에서 left = mid로만 수정하면 탐색 구간이 줄어들지 않는 상황이 발생할 수 있다.

예를 들어 [10, 20]에서 20을 찾으면 처음에는 left = 0, right = 1, mid = 0이다. 10 < 20이므로 오른쪽으로 이동해야 한다. left = mid는 구간을 그대로 두지만, left = mid + 1은 확인한 위치를 제외한다.

경계를 갱신할 때는 정답 후보를 보존하는 것과 구간이 실제로 줄어드는 것을 함께 확인해야 한다.

또한 left === right는 원소가 하나 남은 상태이므로, 이를 검사하기 위해 반복 조건에 등호가 들어간다.

while (left <= right)

범위를 절반으로 줄이면 왜 로그가 나올까?

후보가 16개라고 생각해 보자. 개수를 절반씩 줄이면 16 → 8 → 4 → 2 → 1이다. 네 번 줄이면 하나가 남는다. 32개라면 32 → 16 단계만 하나 더 필요하다.

데이터가 두 배로 늘어도 절반으로 줄이는 횟수는 한 번만 늘어난다. 이것이 로그 증가가 느린 이유다. 실제 이진 탐색은 중앙 원소도 제외하고 중간에 답을 찾으면 끝나므로, 이 숫자는 감소 속도를 이해하기 위한 예시다.

수식으로 확인하기: 절반으로 줄이는 횟수와 로그

처음 후보가 n개라면 반복할 때마다 대략 다음과 같이 줄어든다.

반복 횟수	남은 후보 수
0	n
1	n / 2
2	n / 4
3	n / 8
k	n / 2ᵏ

후보가 하나 정도 남을 때까지 줄인다고 하면 다음 관계가 성립한다.

n / 2ᵏ ≈ 1

이를 정리하면 다음과 같다.

2ᵏ ≈ n

k ≈ log₂ n

즉, log₂ n은 n을 절반씩 줄여 1에 이르는 단계 수를 설명한다. n이 2의 거듭제곱이 아니면 정수가 아닐 수 있으므로, 실제 탐색의 반복 횟수와 정확히 같은 값은 아니다.

여기서 k는 절반으로 줄인 횟수이고, 2ᵏ는 2를 k번 곱한 값이다. log₂ 16 = 4는 “2를 네 번 곱하면 16이 된다”는 뜻이다. ≈는 “대략 같다”로 읽는다. Big O에서는 로그의 밑이 2인지 10인지에 따른 차이가 상수 배수라서 보통 밑을 생략한다.

반복 한 번의 원소 접근과 비교를 O(1)로 가정하면, 최악의 시간 복잡도는 O(log n)이다. 첫 확인에서 찾는 최선의 경우는 O(1)이다. (Cornell University — Analyzing Complexity)

구현 주의점: slice()로 복사하면 전체 비용이 달라진다

반복 횟수가 O(log n)이어도, 매번 slice()로 다음 후보 배열을 복사하면 반복 한 번의 비용이 더 이상 O(1)이 아니다.

slice()는 배열의 일부를 새 배열로 복사하는 메서드다. 범위가 절반으로 줄더라도 그 절반을 복사하는 작업은 원소 수만큼 필요하다.

복사하는 원소 수는 대략 다음과 같다.

n/2 + n/4 + n/8 + …

이 합은 O(n)이다. 따라서 탐색 깊이는 로그 수준이어도 복사까지 포함한 전체 시간은 O(n)이 될 수 있다.

단순히 절반씩 복사하는 모형에서는 원소 16개에 대해 8 + 4 + 2 + 1 = 15개를 복사한다. 실제 탐색은 중앙 원소를 제외하거나 중간에 종료하므로 정확한 복사량은 달라지지만, 최악의 복사 비용이 입력 크기에 비례한다는 점은 같다.

배열을 복사하지 않고 left, right만 변경하는 이유가 여기에 있다.

---

6. 탐색 속도와 전체 비용

정렬 비용도 알고리즘의 일부다

선형 탐색은 최악 O(n), 이진 탐색은 최악 O(log n)이다.

하지만 이진 탐색을 사용하려면 먼저 정렬되어 있어야 한다.

정렬되지 않은 데이터를 한 번 탐색할 때는 다음 두 방법을 비교해야 한다.

방법	전체 비용
바로 선형 탐색	O(n)
정렬 후 이진 탐색	정렬 비용 + O(log n)

정렬 비용을 O(n log n)으로 가정하면 두 번째 방법의 전체 비용은 O(n log n)이다.

탐색 단계만 빠르게 만들었더라도 전체 작업은 더 비쌀 수 있다.

정렬 비용의 전제

JavaScript의 sort()는 특정 시간·공간 복잡도를 보장하지 않는다. 따라서 이 비교의 O(n log n)은 정렬 알고리즘에 대한 가정이며, 모든 엔진에서의 보장은 아니다. (MDN — Array.prototype.sort())

반복 탐색에서는 준비 비용을 재사용할 수 있다

데이터가 바뀌지 않는다면 한 번 정렬한 결과를 여러 번의 탐색에 재사용할 수 있다.

수식으로 비교하기: 같은 데이터에서 q번 탐색

데이터가 바뀌지 않고 탐색을 q번 수행한다면, 각 탐색의 최악 비용을 기준으로 다음처럼 비교할 수 있다.

q는 탐색을 요청한 횟수다. qn은 q × n이고, n log n은 n × log n이다. 한 번 찾는 비용에 탐색 횟수를 곱하되, 처음 한 번만 정렬했다면 정렬 비용은 한 번만 더한다.

선형 탐색을 반복:
O(qn)

한 번 정렬한 뒤 이진 탐색을 반복:
O(n log n + q log n)

탐색 횟수가 충분히 많아지면 처음의 정렬 비용을 감수할 가치가 생긴다.

반대로 데이터가 계속 변경된다면 정렬 상태를 유지하거나 다시 정렬해야 하는 비용이 추가된다.

따라서 선택 기준은 “어떤 탐색이 빠른가”에서 끝나지 않는다.

• 이미 정렬되어 있는가?
• 탐색을 몇 번 수행하는가?
• 데이터가 얼마나 자주 변경되는가?
• 원래 순서를 유지해야 하는가?
• 추가 저장 공간을 사용할 수 있는가?

빠르게 찾는 것과 빠르게 삽입하는 것은 다르다

정렬된 배열에서 새 원소가 들어갈 위치는 삽입 위치를 찾도록 변형한 이진 탐색으로 O(log n)에 찾을 수 있다. 앞의 binarySearch()는 값이 없으면 -1을 반환하므로, 그대로 삽입 위치를 알려 주지는 않는다.

하지만 실제 삽입에는 뒤쪽 원소를 이동하는 비용이 발생할 수 있다.

위치 탐색: O(log n)
실제 삽입: 최악 O(n)

전체: 최악 O(n)

하나의 작업이 여러 단계로 이루어져 있다면 각 단계의 비용을 합쳐야 한다.

이 원리는 프론트엔드에서도 동일하다. 데이터를 찾는 비용만 줄여도, 그 뒤에 전체 배열 복사나 무거운 가공이 있다면 전체 처리 비용은 여전히 클 수 있다.

---

7. 전체 내용 복습

• 시간 복잡도와 Big O: 데이터 개수가 늘 때 작업량이 어떻게 증가하는지 비교한다. Big O는 충분히 큰 입력에서의 상한이며, 최선·평균·최악 중 어떤 상황인지는 별도로 구분한다.
• 상수 생략: 3n + 10은 O(n)으로 표현한다. 3과 10이 실제 시간에 영향을 주지 않는다는 뜻은 아니다.
• 인덱스 접근과 값 탐색: 위치를 알면 일반적인 배열 모델에서 O(1)에 접근한다. 정렬이나 별도의 조회 정보가 없어 선형 탐색을 사용하면 최악 n개를 확인한다.
• 배열의 삽입과 삭제: 앞이나 중간에서는 뒤쪽 원소를 옮기는 비용이 발생한다. 끝에 추가하는 작업은 여유 공간이 있으면 O(1)이다.
• 분할 상환 비용: 용량을 일정 비율로 늘리는 동적 배열에서는 추가 1회당 분할 상환 O(1)이다. 공간 확장이 필요한 개별 추가는 O(n)일 수 있다.
• 선형 탐색: 최선 O(1), 최악 O(n)이다. 값이 한 번 존재하고 각 위치의 확률이 같으면 평균도 O(n)이며, 반복문 구현의 추가 공간은 O(1)이다.
• 배열 메서드의 전체 비용: find() 안에서 includes()를 사용하면 바깥 배열의 길이 n과 안쪽 배열의 길이 m에 따라 최악 O(nm)이 될 수 있다.
• 이진 탐색의 조건과 비용: 같은 기준으로 정렬된 배열에서 정답 후보를 유지하며 범위를 절반씩 줄인다. 반복마다 일정한 비용으로 접근·비교하면 최악 O(log n)이다.
• 이진 탐색의 구현: 가운데 값이 정답이 아니면 경계를 mid + 1 또는 mid - 1로 옮겨 해당 위치를 제외한다. 매번 slice()로 배열을 복사하면 최악의 전체 시간이 O(n)이 될 수 있다.
• 준비와 후속 작업의 비용: 탐색뿐 아니라 정렬·복사·이동 비용도 합쳐야 한다. 이진 탐색으로 삽입 위치를 빠르게 찾아도 실제 원소 이동에는 최악 O(n)이 필요하다.

---

8. 질문

질문 1. Big O에 대한 설명으로 옳은 것은?

1. O(1)인 작업은 언제나 정확히 한 번만 실행된다.
2. O(n)은 언제나 최악의 경우만 나타내는 표기다.
3. 3n + 10을 O(n)으로 표현해도 3과 10은 실제 실행 시간에 영향을 줄 수 있다.
4. O(n²)인 알고리즘은 입력 크기와 관계없이 모든 O(n) 알고리즘보다 느리다.

정답과 해설

정답: 3번

Big O에서는 증가 방식을 비교하기 위해 상수 배수와 작은 항을 생략한다. 실제 작업에서는 이 비용도 발생한다.

• 1번: O(1)은 입력 크기와 무관하게 작업량이 일정한 범위에 머문다는 뜻이다.
• 2번: 최선·평균·최악 각각의 비용을 Big O로 표현할 수 있다.
• 4번: 작은 입력에서는 상수 비용 등의 영향으로 속도 순서가 달라질 수 있다.

질문 2. 배열에 다음 작업을 할 때, 일반적인 동적 배열 모델에서 옳은 설명은?

const numbers = [10, 20, 30];
numbers.unshift(5);

1. 추가한 값이 하나이므로 기존 배열 크기와 관계없이 O(1)이다.
2. 기존 원소 3개의 위치가 뒤로 바뀌며, 기존 원소가 n개라면 이동 비용은 O(n)이다.
3. push(5)도 여유 공간이 있더라도 기존 원소를 모두 뒤로 옮겨야 한다.
4. push()의 분할 상환 O(1)은 모든 개별 추가가 반드시 O(1)이라는 뜻이다.

정답과 해설

정답: 2번

앞에 5를 넣으면 10, 20, 30의 인덱스가 각각 0 → 1, 1 → 2, 2 → 3으로 바뀐다. 일반적인 배열 모델에서는 기존 원소를 이동하는 비용이 필요하다.

• 1번: 새 값을 쓰는 비용 외에 기존 원소를 옮기는 비용이 있다.
• 3번: 끝에 추가하고 여유 공간이 있다면 기존 원소는 옮길 필요가 없다.
• 4번: 공간 확장이 필요한 개별 추가는 O(n)일 수 있다. 분할 상환 비용은 여러 번의 추가 비용을 합쳐 나눈 것이다.

질문 3. 정렬되지 않은 배열에서 값을 한 번만 찾으려 한다. 전체 비용에 대한 설명으로 옳은 것은?

정렬은 O(n log n), 숫자 비교와 인덱스 접근은 O(1)이라고 가정한다. 이진 탐색은 배열을 복사하지 않고 인덱스로 범위를 줄인다.

1. 선형 탐색은 찾는 값이 첫 번째에 있어도 반드시 n개를 모두 확인한다.
2. 정렬 없이 가운데 원소의 값부터 비교하며 절반을 제외해도 항상 올바른 결과를 얻는다.
3. 정렬한 뒤 이진 탐색하면 전체 비용은 정렬 비용과 무관하게 O(log n)이다.
4. 바로 선형 탐색하면 최악 O(n)이고, 정렬 후 이진 탐색하면 전체 O(n log n)이므로 선형 탐색이 더 유리할 수 있다.

정답과 해설

정답: 4번

이진 탐색 단계는 빠르지만 정렬 준비 비용을 포함해야 한다. 한 번만 찾는다면 정렬 없이 순서대로 비교하는 방법이 더 유리할 수 있다.

• 1번: 첫 번째에서 발견하면 바로 종료할 수 있다.
• 2번: 정렬되지 않았다면 제외한 절반에 찾는 값이 있을 수 있다.
• 3번: 전체 비용은 O(n log n) + O(log n)이며, 더 크게 증가하는 정렬 비용이 전체 증가율을 결정한다.

---

참고

• ECMAScript — Indexed Collections
• MDN — Array.prototype.find()
• MDN — Array.prototype.sort()
• V8 — Elements kinds
• Cornell University — Analyzing Complexity
• Cornell University — Loop invariants