선형 탐색은 맨땅에 헤딩하기
크리스는 2장 정렬 파트를 마스터하고 자신감이 넘친다.
"이제 어떤 데이터든 다 다룰 수 있어!"
그런데 회사 DB에서 급하게 데이터를 찾을 일이 생겼다.
"크리스, 유저 ID가 user_9999인 사람 좀 찾아줘. 데이터는 정렬 안 되어 있고 그냥 쌓여있어."
10만 개의 뒤죽박죽 섞인 데이터. 여기서 특정 데이터를 찾으려면 어떻게 해야 할까?
별다른 방법이 없다. 처음부터 끝까지 하나씩 확인해 보는 수밖에.
이것이 바로 우리가 가장 많이 사용하고, 가장 직관적인 선형 탐색(Linear Search)이다.
1. 앞에서부터 하나씩: 단순함의 미학
선형 탐색은 이름 그대로 데이터를 선(Line)처럼 늘어놓고, 처음부터 끝까지 순서대로 훑는 방식이다.
너무 단순해서 "이게 알고리즘이야?" 싶겠지만, 자바스크립트 내장 함수들의 90%는 이 방식을 사용한다.
2. 자바스크립트 속의 선형 탐색
우리가 매일 쓰는 배열 메서드들이 사실은 선형 탐색이다.
const users = ["Alice", "Bob", "Charlie", "Dave", "Eve"];
// 1. indexOf: 값이 있으면 인덱스, 없으면 -1
users.indexOf("Charlie"); // 2
// 2. includes: 값이 있으면 true, 없으면 false
users.includes("Frank"); // false
// 3. find: 조건(콜백)에 맞는 첫 번째 요소 반환
users.find(user => user.startsWith("D")); // "Dave"
// 4. findIndex: 조건에 맞는 첫 번째 인덱스 반환
users.findIndex(user => user === "Eve"); // 4이 모든 메서드는 내부적으로 0번 인덱스부터 length - 1까지 반복문을 돌고 있다.
3. 직접 구현해 보기
원리를 이해하기 위해 간단하게 구현해 보자.
function linearSearch(arr, value) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === value) {
return i; // 찾으면 인덱스 반환
}
}
return -1; // 끝까지 없으면 -1
}
linearSearch([10, 50, 30, 70, 80], 30); // 24. 성능 분석: 빅오(Big-O)
선형 탐색의 성능은 "찾는 물건이 어디에 있느냐에 따라 극과 극이다.
즉, 데이터가 10배 늘어나면 찾는 시간도 10배 늘어난다.
데이터가 정렬되어 있지 않다면 선형 탐색 외에는 방법이 없다. 가장 정직하고 확실한 방법이다.
5. 언제 써야 할까?
핵심 정리
"그런데 데이터가 100만 개라면? 맨 뒤에 있는 걸 찾으려면 100만 번 확인해야 하잖아. 너무 느린데?"
만약 데이터가 정렬되어 있다면, 우리는 훨씬 더 스마트한 방법을 쓸 수 있다.
업다운(Up-Down) 게임의 필승 전략, 반씩 뚝뚝 잘라내는 이진 탐색(Binary Search)을 만나보자.