EN
JP
KR선형 탐색이란? JavaScript로 Linear Search 구현하기
선형 탐색은 탐색 알고리즘 중 가장 기본적인 방식입니다. 배열이나 리스트의 앞에서부터 하나씩 요소를 확인하면서 원하는 값이나 조건에 맞는 요소를 찾습니다. 영어로는 Linear Search라고 하며, 한국어로는 선형 탐색 또는 순차 탐색이라고 부릅니다. 데이터가 정렬되어 있을 필요가 없기 때문에 어떤 순서의 데이터에도 사용할 수 있으며, 구현이 매우 단순해 알고리즘 입문에서 자주 다뤄집니다.
JavaScript에서는 선형 탐색과 유사한 개념을 가진 내장 메서드가 많습니다. includes()는 값이 포함되어 있는지 확인하고, find()는 조건에 맞는 첫 번째 요소를 반환하며, findIndex()는 조건에 맞는 첫 번째 위치를 반환합니다. filter()는 조건에 맞는 모든 요소를 반환합니다. 실무에서는 직접 선형 탐색 함수를 작성하기보다 이런 메서드를 사용하는 경우가 많지만, 선형 탐색의 구조를 이해하면 각 메서드의 동작 방식과 성능 특성을 더 명확하게 이해할 수 있습니다.
1. 선형 탐색이란?
선형 탐색은 데이터를 처음부터 끝까지 순서대로 확인하며 원하는 값을 찾는 알고리즘입니다. 예를 들어 [10, 20, 30, 40]이라는 배열에서 30을 찾는다면, 먼저 10을 확인하고, 다음으로 20을 확인한 뒤, 30을 찾으면 탐색을 종료합니다. 이처럼 한 방향으로 순차적으로 진행하기 때문에 이해하기 쉽고 구현도 간단합니다.
선형 탐색의 가장 큰 장점은 데이터가 정렬되어 있지 않아도 사용할 수 있다는 점입니다. 이진 탐색처럼 정렬을 전제로 하지 않기 때문에 API에서 받은 데이터, 사용자 입력 순서가 중요한 데이터, 임시 배열 등 다양한 상황에 바로 적용할 수 있습니다. 반면 데이터가 많아지면 확인해야 하는 요소 수도 많아지므로 성능에 주의해야 합니다.
1.1 선형 탐색의 기본 이미지
선형 탐색의 기본 흐름은 “찾을 때까지 하나씩 확인한다”입니다. 배열의 첫 번째 요소부터 시작해 목표 값과 같은지 비교하고, 같지 않으면 다음 요소로 이동합니다. 일치하는 요소를 찾으면 그 위치나 요소를 반환하고, 끝까지 찾지 못하면 -1, undefined, null 같은 값을 반환합니다.
이 과정은 사람이 목록을 위에서 아래로 읽으며 항목을 찾는 방식과 비슷합니다. 작은 목록에서는 매우 자연스럽고 충분히 빠릅니다. 그러나 목록이 매우 크고 원하는 값이 뒤쪽에 있거나 존재하지 않는다면 전체를 확인해야 하므로 비용이 커집니다.
1.2 JavaScript 메서드와의 관계
JavaScript의 includes(), indexOf(), find(), findIndex(), some()은 선형 탐색과 밀접한 관련이 있습니다. 이 메서드들은 보통 앞에서부터 요소를 확인하다가 조건이 만족되면 결과를 반환합니다. 예를 들어 find()는 조건을 만족하는 첫 번째 요소를 찾으면 즉시 종료하고, some()은 조건을 만족하는 요소가 하나라도 있으면 true를 반환합니다.
반면 filter()는 조건에 맞는 모든 요소를 찾아야 하므로 끝까지 확인합니다. 따라서 첫 번째 요소만 필요할 때 filter()를 사용하면 불필요한 탐색이 발생할 수 있습니다. 선형 탐색의 개념을 이해하면 이런 메서드의 차이를 더 정확하게 구분할 수 있습니다.
2. 선형 탐색의 기본 아이디어
선형 탐색은 순차적인 비교를 기반으로 합니다. 배열이라면 인덱스 0부터 시작해 array[0], array[1], array[2]처럼 차례대로 값을 확인합니다. 현재 요소가 목표 값과 일치하면 탐색을 종료하고 결과를 반환합니다. 일치하지 않으면 다음 요소로 넘어갑니다. 배열 끝까지 확인했는데도 찾지 못했다면 찾지 못했다는 결과를 반환합니다.
이 방식은 데이터 순서에 대한 가정이 필요 없습니다. 배열이 오름차순이든 내림차순이든, 랜덤한 순서이든 상관없이 작동합니다. 또한 숫자, 문자열, 객체, 복잡한 조건에도 적용할 수 있습니다. 조건을 자유롭게 작성할 수 있다는 점은 선형 탐색의 중요한 장점입니다.
2.1 일치하면 바로 종료한다
첫 번째 일치 결과만 필요하다면, 선형 탐색은 값을 찾은 순간 종료할 수 있습니다. 이 덕분에 목표 값이 앞쪽에 있을 때는 매우 빠르게 끝납니다. JavaScript의 find()와 some()도 이와 같은 방식으로 동작합니다.
하지만 목표 값이 배열의 마지막에 있거나 아예 존재하지 않는 경우에는 모든 요소를 확인해야 합니다. 따라서 선형 탐색의 실제 성능은 데이터 크기뿐 아니라 목표 값의 위치에도 영향을 받습니다.
2.2 복잡한 조건 검색에 적합하다
선형 탐색은 단순 값 비교뿐 아니라 복잡한 조건 검색에도 적합합니다. 예를 들어 사용자 배열에서 role이 "admin"이고 active가 true인 사용자를 찾거나, 상품 목록에서 재고가 있고 가격이 특정 금액 이하인 상품을 찾는 경우에도 사용할 수 있습니다.
이런 조건은 이진 탐색으로 처리하기 어렵습니다. 이진 탐색은 정렬된 기준을 바탕으로 범위를 절반씩 줄이는 방식이므로, 복합 조건이나 유연한 조건 검색에는 선형 탐색이 더 자연스럽습니다.
3. 언제 선형 탐색을 사용하는가?
선형 탐색은 데이터가 작거나, 정렬되어 있지 않거나, 검색 조건이 복잡하거나, 검색이 한 번만 발생하는 경우에 적합합니다. 예를 들어 수십 개 정도의 메뉴 항목, 권한 목록, 태그 목록, 선택지 배열을 검색하는 경우에는 선형 탐색으로 충분합니다. 이런 경우 복잡한 알고리즘이나 자료구조를 도입하는 것보다 find()나 includes()를 사용하는 것이 더 읽기 쉽고 유지보수하기 좋습니다.
또한 정렬되지 않은 데이터를 그대로 유지해야 하는 경우에도 선형 탐색이 적합합니다. 데이터의 순서가 등록순, 표시순, 사용자 입력순처럼 의미를 가진다면 이진 탐색을 위해 정렬하는 것이 오히려 문제를 만들 수 있습니다. 이런 상황에서는 원본 순서를 유지하면서 조건에 맞는 값을 찾는 선형 탐색 방식이 안전합니다.
3.1 작은 데이터의 경우
데이터가 작으면 선형 탐색은 매우 실용적입니다. 10개, 20개 정도의 배열에서는 O(n)과 O(log n)의 차이가 체감되지 않는 경우가 많습니다. 오히려 코드가 단순하고 의도가 명확한 것이 더 중요합니다.
실무에서는 불필요한 최적화가 코드를 복잡하게 만드는 경우가 많습니다. 작은 데이터라면 includes(), find(), filter() 같은 표준 메서드를 사용해 간결하게 작성하는 것이 좋습니다.
3.2 정렬되지 않은 데이터의 경우
선형 탐색은 정렬되지 않은 데이터에서도 그대로 사용할 수 있습니다. API 응답 순서가 중요하거나, 사용자가 직접 정렬한 순서를 보존해야 하는 경우에는 데이터를 정렬하지 않고 그대로 검색하는 것이 좋습니다.
정렬이 필요 없는 점은 선형 탐색의 큰 장점입니다. 이진 탐색을 사용하려면 데이터 정렬이 필요하고, 정렬 비용과 원본 순서 변경 문제를 고려해야 합니다. 따라서 정렬되지 않은 데이터에서는 선형 탐색이 더 자연스러운 선택이 됩니다.
4. JavaScript로 선형 탐색 작성하기
JavaScript에서 선형 탐색은 for문으로 쉽게 작성할 수 있습니다. 알고리즘 학습에서는 직접 반복문을 작성하면 요소가 어떤 순서로 확인되는지 명확하게 이해할 수 있습니다. 실무에서는 같은 작업을 find(), findIndex(), includes() 같은 표준 메서드로 더 간단하게 표현하는 경우가 많습니다.
선형 탐색 함수를 작성할 때는 반환값을 먼저 정해야 합니다. 인덱스를 반환할 것인지, 요소 자체를 반환할 것인지, 존재 여부만 반환할 것인지, 일치하는 모든 결과를 반환할 것인지에 따라 함수 구조가 달라집니다. 목적에 맞는 반환값을 설계해야 재사용하기 좋은 함수가 됩니다.
4.1 인덱스를 반환하는 구현
function linearSearch(array, target) { for (let i = 0; i < array.length; i++) { if (array[i] === target) { return i; } } return -1;}console.log(linearSearch([4, 2, 7, 1], 7)); // 2console.log(linearSearch([4, 2, 7, 1], 9)); // -1
이 구현은 indexOf()와 비슷하게 동작합니다. 찾으면 첫 번째 위치를 반환하고, 찾지 못하면 -1을 반환합니다. 가장 기본적인 선형 탐색 예제입니다.
4.2 요소 자체를 반환하는 구현
function findUserById(users, targetId) { for (const user of users) { if (user.id === targetId) { return user; } } return undefined;}const users = [ { id: 1, name: "Sato" }, { id: 2, name: "Tanaka" }];console.log(findUserById(users, 2)); // { id: 2, name: "Tanaka" }
객체 배열에서는 인덱스보다 요소 자체가 필요한 경우가 많습니다. 이 구현은 find()와 비슷하게 동작하며, 조건에 맞는 첫 번째 객체를 반환합니다.
5. 첫 번째 일치 요소 찾기
선형 탐색에서는 조건에 맞는 첫 번째 요소만 필요할 때, 찾은 즉시 탐색을 종료할 수 있습니다. 예를 들어 사용자 ID가 고유하다면 해당 ID의 사용자를 찾은 뒤 더 이상 배열을 확인할 필요가 없습니다. 이 경우 find()나 findIndex()를 사용하는 것이 적합합니다.
첫 번째 일치 요소를 찾는 방식은 불필요한 반복을 줄일 수 있습니다. 반대로 조건에 맞는 모든 요소가 필요하다면 첫 번째 결과에서 멈추면 안 됩니다. 따라서 검색 목적이 단일 결과인지 전체 결과인지 구분하는 것이 중요합니다.
5.1 find 사용하기
const products = [ { id: 1, name: "Book", price: 1200 }, { id: 2, name: "Pen", price: 200 }];const product = products.find(item => item.id === 2);console.log(product); // { id: 2, name: "Pen", price: 200 }
find()는 조건을 만족하는 첫 번째 요소를 반환합니다. 찾지 못하면 undefined를 반환합니다. 요소 자체가 필요할 때 가장 많이 사용되는 메서드입니다.
5.2 findIndex 사용하기
const scores = [70, 85, 90, 60];const index = scores.findIndex(score => score >= 90);console.log(index); // 2
요소 자체가 아니라 위치가 필요하다면 findIndex()를 사용합니다. 요소를 수정하거나 삭제하거나 특정 위치를 기준으로 처리해야 할 때 유용합니다.
6. 일치하는 모든 위치 찾기
때로는 첫 번째 결과가 아니라 모든 일치 결과가 필요합니다. 예를 들어 배열 안에 같은 값이 여러 번 등장할 때 모든 위치를 찾거나, 사용자 목록에서 특정 역할을 가진 모든 사용자를 가져오는 경우가 있습니다. 이때는 첫 번째 일치에서 종료하지 않고 배열 끝까지 탐색해야 합니다.
이 방식은 항상 전체 배열을 확인하므로 시간 복잡도는 O(n)입니다. JavaScript에서는 모든 일치 요소를 가져올 때 filter()를 자주 사용합니다. 위치까지 필요하다면 반복문으로 직접 인덱스를 수집할 수 있습니다.
6.1 모든 인덱스를 반환하기
function findAllIndexes(array, target) { const indexes = []; for (let i = 0; i < array.length; i++) { if (array[i] === target) { indexes.push(i); } } return indexes;}console.log(findAllIndexes([1, 3, 1, 5, 1], 1)); // [0, 2, 4]
이 구현은 일치하는 값을 찾더라도 탐색을 멈추지 않습니다. 모든 위치를 얻기 위해 끝까지 확인합니다.
6.2 filter로 모든 요소 가져오기
const users = [ { name: "Sato", role: "admin" }, { name: "Tanaka", role: "viewer" }, { name: "Suzuki", role: "admin" }];const admins = users.filter(user => user.role === "admin");console.log(admins);
filter()는 조건을 만족하는 모든 요소를 새 배열로 반환합니다. 단 하나의 결과만 필요하다면 find()를 사용하는 것이 더 적절합니다.
7. 선형 탐색의 시간 복잡도
선형 탐색의 시간 복잡도는 O(n)입니다. 데이터가 n개 있을 때, 최악의 경우 n개 모두를 확인해야 한다는 뜻입니다. 목표 값이 첫 번째 요소에 있으면 한 번의 비교로 끝나지만, 마지막에 있거나 존재하지 않으면 모든 요소를 확인해야 합니다. 따라서 데이터 양이 증가하면 처리 시간도 비례해 증가합니다.
공간 복잡도는 첫 번째 결과만 찾는 경우 보통 O(1)입니다. 추가적인 큰 자료구조를 만들지 않고 몇 개의 변수만 사용하기 때문입니다. 그러나 모든 일치 결과를 배열에 저장한다면 결과 개수에 따라 추가 메모리가 필요합니다.
7.1 최선의 경우와 최악의 경우
최선의 경우는 목표 값이 첫 번째 요소에 있는 경우입니다. 이때는 비교 한 번으로 끝납니다. 최악의 경우는 목표 값이 마지막에 있거나 아예 존재하지 않는 경우입니다. 이때는 모든 요소를 확인해야 합니다.
평균적으로는 목표 값이 랜덤한 위치에 있다고 가정할 때 배열의 절반 정도를 확인할 수 있습니다. 하지만 Big-O 표기에서는 입력 크기에 비례하므로 O(n)으로 표현합니다.
7.2 이진 탐색과의 차이
선형 탐색은 O(n), 이진 탐색은 O(log n)입니다. 이 차이는 데이터가 커질수록 커집니다. 예를 들어 100만 개의 정렬 데이터에서 값을 찾을 때, 선형 탐색은 최악의 경우 100만 번 가까이 확인할 수 있지만, 이진 탐색은 약 20번 정도의 비교로 찾을 수 있습니다.
하지만 이진 탐색은 정렬된 데이터에서만 사용할 수 있습니다. 선형 탐색은 정렬되지 않은 데이터에서도 사용할 수 있기 때문에 더 유연합니다. 따라서 단순히 계산량만 보고 선택하기보다 데이터 상태와 검색 목적을 함께 고려해야 합니다.
8. 장점과 단점
선형 탐색의 장점은 단순함과 유연성입니다. 구현이 쉽고, 데이터가 정렬되어 있지 않아도 사용할 수 있으며, 복잡한 조건 검색에도 잘 맞습니다. JavaScript의 표준 메서드와도 자연스럽게 연결되기 때문에 실무에서 자주 사용됩니다.
단점은 데이터가 많아질수록 느려질 수 있다는 점입니다. 매번 앞에서부터 하나씩 확인하기 때문에 큰 배열을 반복 검색하면 비용이 커집니다. 특히 ID로 객체를 자주 찾는 경우에는 Map으로 변환하는 것이 더 효율적일 수 있습니다.
8.1 장점
선형 탐색은 매우 이해하기 쉽습니다. 정렬이나 전처리가 필요 없으며, 데이터를 받은 그대로 검색할 수 있습니다. 작은 배열에서는 충분히 빠르고, 코드도 간결하게 유지할 수 있습니다.
또한 검색 조건을 자유롭게 작성할 수 있습니다. 단순 값 비교뿐만 아니라 문자열 포함 여부, 객체 속성 조건, 여러 조건 조합에도 쉽게 대응할 수 있습니다.
8.2 단점
가장 큰 단점은 큰 데이터에서 느려질 수 있다는 것입니다. 데이터 수가 늘어나면 확인해야 할 요소 수도 늘어납니다. 찾는 값이 없으면 항상 끝까지 확인해야 합니다.
반복 검색이 많다면 Set, Map, 이진 탐색 같은 다른 방법을 검토해야 합니다. 선형 탐색은 기본적이고 유용하지만, 모든 상황에서 최적은 아닙니다.
마치며
선형 탐색은 데이터를 앞에서부터 순서대로 확인하여 원하는 값이나 조건에 맞는 요소를 찾는 가장 기본적인 탐색 알고리즘입니다. 정렬이 필요 없고 구현이 단순하며, 복잡한 조건 검색에도 잘 맞기 때문에 JavaScript에서 매우 자주 사용됩니다. includes(), find(), findIndex(), filter() 같은 표준 메서드도 선형 탐색의 개념과 깊게 연결되어 있습니다.
시간 복잡도는 O(n)이므로 데이터가 커질수록 비용이 증가합니다. 작은 데이터나 한 번의 검색에는 충분하지만, 큰 데이터를 반복 검색한다면 Map이나 Set 같은 자료구조를 고려해야 합니다. 정렬된 데이터에서 빠른 검색이 필요하다면 이진 탐색도 선택지가 될 수 있습니다.
실무에서는 선형 탐색을 직접 구현하기보다 표준 메서드를 사용하는 경우가 많습니다. 그러나 선형 탐색의 동작 원리를 이해하면 어떤 메서드가 언제 적절한지, 어떤 상황에서 성능 문제가 발생할 수 있는지 더 잘 판단할 수 있습니다.
