탐색: 선형 탐색

 

선형 탐색이란?

선형 탐색(Linear Search), 또는 순차 탐색(Sequential Search)은 가장 기본적인 탐색 알고리즘 중 하나로, 데이터 집합에서 특정 값을 찾기 위해 원소를 하나씩 순차적으로 확인하는 방법입니다. 복잡한 자료구조나 알고리즘을 사용하지 않고, 시작부터 끝까지 원소를 차례대로 탐색합니다.

 

선형 탐색의 작동 원리

선형 탐색은 배열이나 리스트 등의 자료구조에 저장된 데이터를 처음부터 끝까지 차례로 검사하여 원하는 값을 찾습니다. 찾고자 하는 값이 발견되면, 그 값의 위치(인덱스)를 반환하고 탐색을 종료합니다. 만약 리스트 전체를 탐색했음에도 불구하고 해당 값이 없다면, 탐색 실패를 의미하는 특정 값을 반환합니다.

 

선형 탐색의 단계별 과정

1. 데이터 집합의 첫 번째 원소부터 시작합니다.
2. 현재 원소가 찾고자 하는 값과 일치하는지 확인합니다.
3. 값이 일치한다면, 현재 원소의 위치를 반환하고 탐색을 종료합니다.
4. 값이 일치하지 않으면, 다음 원소로 이동하여 과정을 반복합니다.
5. 데이터 집합의 끝까지 탐색했음에도 값을 찾지 못했다면, 탐색 실패를 의미하는 값을 반환합니다.

선형 탐색의 복잡도

시간 복잡도: 최악의 경우 O(n), 최선의 경우 O(1)입니다.
공간 복잡도: O(1)로, 추가적인 메모리 공간이 필요 없습니다.

---

Pseudocode

function linearSearch(arr, target) {
  for i = 0 to length(arr) - 1
    if arr[i] == target
      return i // 찾은 경우 인덱스 반환
  return -1 // 찾지 못한 경우 -1 반환
}

 

실제 예시로 이해하기

예를 들어, [5, 8, 1, 15, 22, 3] 배열에서 15라는 값을 찾고자 한다고 가정해봅시다.

1. 배열의 첫 번째 원소부터 15라는 값을 찾습니다.
2. 4번째 원소(인덱스 3)에서 15라는 값을 찾았으므로, 인덱스 3을 반환합니다.
3. 탐색을 종료합니다.

선형 탐색은 구현이 간단하며 정렬되지 않은 데이터 집합에서도 사용할 수 있는 장점이 있습니다. 하지만 데이터의 양이 많을수록 탐색에 필요한 시간이 길어지는 단점이 있어, 대규모 데이터 집합에는 다른 탐색 기법이 더 효율적일 수 있습니다.