검색 알고리즘 - 선형 검색

선형 검색

순차 검색이라고도 하는 선형 검색은 가장 간단한 검색 알고리즘 중 하나이다. 목록에서 특정 요소를 찾는 데 사용되며, 일치하는 항목을 찾거나 모든 요소가 검색될 때까지 목록의 각 요소를 대상 값과 순차적으로 비교한다.

선형 검색 작동 방식

• 첫 번째 요소에서 시작: 목록 또는 배열의 첫 번째 요소에서 시작
• 각 요소를 대상과 비교: 현재 요소를 검색 중인 대상 요소와 비교한다.
• 다음 요소로 이동: 현재 요소가 대상이 아닌 경우 목록의 다음 요소로 이동한다.
• 찾거나 끝날 때까지 반복: 요소를 찾거나 목록 끝에 도달할 때까지 이 프로세스가 지속된다.
• 결과 반환: 대상 요소를 찾으면 해당 요소의 인덱스나 성공을 나타내는 플래그를 반환한다. 대상을 찾지 못한 채 목록의 끝에 도달하면 실패를 나타내는 플래그나 -1과 같은 특수 값을 반환한다.

복잡도

• 시간 복잡도
  • 최선의 경우: O(1) - 대상 요소가 목록의 첫 번째 요소일 때 발생한다.
  • 평균 및 최악의 경우: O(n) - 여기서 n은 목록의 총 요소 수이다.
• 공간 복잡도: O(1)

장단점

• 장점
  • 단순성: 선형 검색은 간단하고 구현하기 쉽다.
  • 유연성: 선형 검색은 정렬 여부, 링크 기반 또는 배열 기반 목록에 관계없이 모든 목록에서 사용할 수 있다. 가장 보편적인 검색 알고리즘이다.
• 단점
  • 대규모 데이터세트의 비효율성: 선형 검색의 주요 단점은 대규모 데이터세트를 처리할 때의 비효율성이다. 검색에 걸리는 시간은 요소 수에 따라 선형적으로 증가하며, 큰 목록의 경우 엄청나게 느려질 수 있다.
  • 확장 불가능: 선형 시간 복잡도로 인해 선형 검색의 성능은 데이터 세트 크기가 증가함에 따라 빠르게 저하된다. 이로 인해 확장성이 중요하거나 데이터 크기가 커질 수 있는 애플리케이션에는 적합하지 않다.

예시 코드

def linear_search(arr, target):
  for i in range(len(arr)):
    if arr[i] == target:
      return i  # Target found, return its index
  return -1  # Target not found in the array

arr = [12, 11, 13, 5, 6, 7]
target = 5
result = linear_search(arr, target)

if result != -1:
  print(f"Element found at index {result}")
else:
  print("Element not found in the array")