검색 알고리즘 - 선형 검색의 이해와 효율적 구현 방법

선형 검색 개요

• 순차적으로 배열의 요소를 검사하여 목표 값을 찾는 방식으로 동작합니다.

선형 검색 동작 원리

1. 배열이나 리스트의 첫 번째 요소부터 시작하여 마지막 요소까지 하나씩 순차적으로 검색합니다.
2. 각 요소를 검색하면서 찾고자 하는 값을 확인합니다.
3. 원하는 값을 찾으면 해당 요소의 인덱스를 반환하고 검색을 종료합니다.
4. 배열의 마지막 요소까지 검사했는데도 목표 값을 찾지 못하면 -1을 반환합니다.

선형 검색 코드 예시

function test(arr, target) {
 const n = arr.length
 for(let i = 0; i < n; i++) {
  if(arr[i] === target) return i
 }
 return -1
}

const arr = [5,4,3,2,1]
const target = 3
test(arr, target)

선형 검색 시간 복잡도

• 목표 값이 첫 번째인 경우(최선) O(1)
• 평균과 최악의 경우 O(n)

선형 검색 장점

• 구현이 간단합니다.
• 정렬되지 않은 배열에서도 검색할 수 있습니다.

선형 검색 단점

• 시간 복잡도가 O(n)으로 비효율적입니다.
• 배열의 크기가 클수록 검색 시간이 오래 걸립니다.

선형 검색 활용

• 이해하기 쉬워서 알고리즘 학습의 첫 걸음으로 활용됩니다.
• 작은 크기의 배열에서 검색할 때 사용할 수 있습니다.