선형 탐색
마지막 업데이트
선형 탐색(순차 탐색이라고도 함)은 가장 단순한 탐색 알고리즘입니다. 첫 번째 요소에서 시작해 일치하는 값을 찾거나 요소가 다 떨어질 때까지 각 요소를 목표 값과 비교합니다. 데이터에 대해 아무런 가정도 하지 않습니다 — 배열은 정렬되어 있지 않아도 되고, 요소는 같은지 비교할 수 있는 것이라면 무엇이든 됩니다.
위 애니메이션은 탐색이 왼쪽에서 오른쪽으로 진행되는 동안 각 비교를 강조 표시하고, 목표 값이 나타나는 순간 멈춥니다. 단순함의 대가는 속도입니다. 최악의 경우 모든 요소를 확인해야 하므로 O(n) 시간에 동작합니다. 데이터가 정렬되어 있다면 이진 탐색이 같은 답을 O(log n)에 찾습니다 — 먼저 정렬된 데이터가 필요하다면 병합 정렬을 참고하세요.
시간 및 공간 복잡도
| 경우 | 복잡도 | 비고 |
|---|---|---|
| 최선의 경우 | O(1) | 첫 번째 요소가 목표 값인 경우. |
| 평균적인 경우 | O(n) | 평균적으로 요소의 절반을 확인한 뒤 목표 값을 찾는다. |
| 최악의 경우 | O(n) | 목표 값이 마지막에 있거나 — 아예 없는 경우. |
| 공간 | O(1) | 현재 인덱스만 유지한다. |
단계별 과정
| 단계 | 무슨 일이 일어나는가 |
|---|---|
| 1 | 배열의 첫 번째 요소인 인덱스 0에서 시작한다. |
| 2 | 현재 요소를 목표 값과 비교한다. |
| 3 | 같으면 현재 인덱스를 반환한다 — 발견. |
| 4 | 그렇지 않으면 한 칸 오른쪽으로 이동해서 반복한다. |
| 5 | 일치하는 값 없이 배열 끝에 도달하면 목표 값이 없는 것이다(-1 반환). |
풀이 예제
[7, 3, 9, 1, 5, 8, 2]에서 5를 탐색하는 경우:
| 비교 | 인덱스 | 요소 | 결과 |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5 — 계속 탐색. |
| 2 | 1 | 3 | 3 ≠ 5 — 계속 탐색. |
| 3 | 2 | 9 | 9 ≠ 5 — 계속 탐색. |
| 4 | 3 | 1 | 1 ≠ 5 — 계속 탐색. |
| 5 | 4 | 5 | 5 = 5 — 인덱스 4에서 발견. |
선형 탐색을 사용해야 할 때
| 사용해야 할 때 | 피해야 할 때 |
|---|---|
| 데이터가 정렬되어 있지 않거나 끊임없이 변할 때 | 데이터가 정렬되어 있을 때 — 이진 탐색이 지수적으로 더 빠르다 |
| 컬렉션이 작아서 단순함이 이길 때 | 데이터셋이 크고 반복적으로 탐색될 때 |
| 순차 접근만 가능할 때(스트림, 연결 리스트) | O(1) 조회를 위한 인덱스나 해시 테이블을 마련할 수 있을 때 |
Linear Search 코드
Python, JavaScript, Java, C++, C, Pseudocode로 작성된 깔끔하고 실행 가능한 Linear Search 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Linear Search 코드
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))JavaScript로 구현한 Linear Search 코드
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Java로 구현한 Linear Search 코드
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}C++로 구현한 Linear Search 코드
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}C로 구현한 Linear Search 코드
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Pseudocode로 구현한 Linear Search 코드
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)선형 탐색 FAQ
선형 탐색의 시간 복잡도는 어떻게 되나요?
평균과 최악의 경우
O(n)입니다 — 탐색이 모든 요소를 방문해야 할 수도 있기 때문입니다. 첫 번째 요소가 목표 값인 최선의 경우는 O(1)입니다. 추가 공간은 O(1)을 사용합니다.선형 탐색에는 정렬된 데이터가 필요한가요?
아니요 — 그것이 가장 큰 장점입니다. 선형 탐색은 각 요소가 같은지 확인하기 때문에 완전히 정렬되지 않은 데이터에서도 동작합니다. 순서는 전혀 중요하지 않습니다. 반면 이진 탐색은 정렬된 배열에서만 동작합니다.
선형 탐색이 이진 탐색보다 나은 경우는 언제인가요?
데이터가 정렬되어 있지 않고 한 번만 탐색할 때(먼저 정렬하면
O(n log n)이 듭니다), 컬렉션이 아주 작을 때, 또는 스트림이나 연결 리스트처럼 순차 접근만 가능할 때입니다. 정렬된 배열에서 반복 조회한다면 이진 탐색이 이깁니다.선형 탐색과 순차 탐색은 같은 건가요?
네 — 두 이름은 같은 알고리즘을 설명합니다. 목표 값을 찾거나 컬렉션이 끝날 때까지 요소를 순서대로 훑는 것입니다.
선형 탐색은 평균적으로 몇 번 비교하나요?
목표 값이 존재하고 어느 위치에나 있을 확률이 같다면 평균 약
n/2번 비교합니다. 목표 값이 없으면 정확히 n번입니다. 이 선형적 증가가 선형 탐색이라는 이름의 유래입니다.관련 자료
더 많은 시각화
