Quick Syntax
csharp
static int FindIndex(int[] values, int target)
{
for (int i = 0; i < values.Length; i++)
{
if (values[i] == target) return i;
}
return -1;
}정렬되지 않은 데이터에서 한 번 찾거나 입력이 작으면 O(n) 선형 탐색이 가장 직접적입니다. 정렬 O(n log n)이나 hash table O(n) 준비 비용은 반복 조회가 있을 때 회수할 수 있습니다.
선택 기준
| 상황 | 선택 |
|---|---|
| 작은 collection에서 한 번 조회 | 선형 탐색 |
| 조건을 만족하는 첫 원소 찾기 | 선형 탐색 |
| 정렬된 배열에서 반복 조회 | 이진 탐색 검토 |
| 순서 없이 포함 여부를 반복 조회 | hash set 검토 |
| 원본 순서를 바꾸면 안 됨 | 선형 탐색 또는 별도 index |
최선은 첫 원소에서 O(1), 최악은 끝까지 보거나 없어서 O(n)입니다. 평균 횟수는 target 분포에 따라 달라지며, 중간에 답을 찾으면 즉시 종료합니다.
자주 틀리는 점
- 한 번 찾기 위해 먼저 정렬하고 이진 탐색해 전체 비용을 키우지 않습니다.
- 값이 없을 때 반환할 sentinel과 유효 index를 구분합니다.
- 모든 일치 위치가 필요한 문제에서 첫 값만 찾고 끝내지 않습니다.
- 반복 lookup이 많아지면 같은 O(n) 순회를 계속하는지 확인합니다.
참고 링크
1 sources