Linear search
선형 탐색
앞에서부터 하나씩 비교해요
배열에서 9을 찾아요
찾는 값9
확인한 원소0
현재 값—
현재 위치비교 대상확인한 값
예제 코드
C++
<vector>int linear_search(const std::vector<int>& a, int target) { for (int i = 0; i < static_cast<int>(a.size()); ++i) { if (a[i] == target) return i; } return -1;}Python
def linear_search(a, target): for i, value in enumerate(a): if value == target: return i return -1시작하기
처음부터 살펴봐요
9을 찾아요. 정렬되지 않은 배열도 첫 원소부터 하나씩 비교할 수 있어요.
사용 조건
배열에서 특정 값의 위치를 찾을 때 사용해요. 값이 정렬되어 있지 않아도 사용할 수 있어요.
먼저 알아두면 좋아요
배열의 인덱스와 반복문을 알고 시작해요. 인덱스는 0부터 세요.
동작 원리
첫 원소부터 찾는 값과 비교해요. 같으면 해당 인덱스를 반환하고 끝내요.
다르면 다음 원소로 이동해요. 끝까지 찾지 못했다면 −1처럼 약속한 값을 반환해요. 같은 값이 여러 개면 이 예제는 가장 먼저 나온 위치를 반환해요.
- 시간
- O(n) · 끝까지 보면 원소 n개를 비교해요
- 추가 공간
- O(1) · 인덱스만 추가로 관리해요
주의할 점
- 값과 인덱스를 구분해요. 9를 찾았어도 반환하는 값은 그 위치의 번호예요.
- 값이 없을 때 반환할 값을 정해요. 범위 밖의 원소를 읽지 않아요.