선형탐색(Linear Search)

배열/리스트에서 특정한 값을 찾기 위해 처음부터 끝까지 순차적으로 확인하는 탐색 방법

• 정렬이 되지 않은 상태의 배열/리스트에서 값을 찾기 위한 탐색에 사용
• indexOf(), lastIndexOf(), includes(), find(), findIndex(), some(), every() 등의 js 내장 메소들을 통하여 탐색 가능
• 장점
  • 구현이 간단하고 직관적
  • 리스트가 정렬되어있지 않아도 사용 가능
  • 작은 데이터셋에 효율적
• 단점
  • 시간복잡도가 O(n)으로 데이터가 많아질수록 검색 시간이 선형적으로 증가

진행 과정

1. 탐색할 인덱스 변수를 선언 후 배열의 첫 번째 원소부터 비교 시작
2. 루프를 돌며 현재 값이 찾는 값과 같은지 비교
   • 만약 같다면 현재 인덱스 반환 후 탐색 종료
   • 다르면 다음 요소로 이동하여 탐색 계속 진행
3. 배열의 끝까지 탐색했는데도 찾는 값이 없으면 -1 반환

구현 코드

const linearSearch = (arr, target) => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // 찾으면 인덱스 반환
  }
  return -1; // 못 찾으면 -1 반환
};

const array = [10, 20, 30, 40, 50];
console.log(linearSearch(array, 30)); // 2
console.log(linearSearch(array, 100)); // -1

시간 복잡도 및 공간 복잡도

• 시간 복잡도
  • 최선: O(1)
  • 평균: O(n)
  • 최악: O(n)
• 공간 복잡도