선형 탐색 (Linear Search)

선형 탐색(Linear Search)은 가장 기본적인 탐색 알고리즘 중 하나로, 리스트나 배열에서 특정 값을 찾기 위해 처음부터 끝까지 순차적으로 비교하는 방식으로 동작한다. 이 알고리즘은 정렬되지 않은 리스트에서도 동작하며, 매우 간단한 구현이 가능하지만 효율성은 떨어질 수 있다.

설명 및 개념

선형 탐색은 다음과 같은 단계를 따른다:

1. 초기화: 리스트의 첫 번째 요소부터 시작한다.
2. 비교: 현재 요소와 찾고자 하는 값을 비교한다.
3. 일치 여부 확인:
   • 현재 요소가 찾고자 하는 값과 일치하면, 해당 요소의 인덱스를 반환한다.
   • 일치하지 않으면, 다음 요소로 이동한다.
4. 리스트 끝까지 반복: 리스트의 끝까지 이 과정을 반복한다.
5. 결과 반환: 리스트의 모든 요소를 검사한 후에도 찾고자 하는 값이 없으면, -1을 반환하여 값을 찾을 수 없음을 알린다.

시간 복잡도

선형 탐색의 시간 복잡도는 다음과 같다:

• 최선의 경우 (Best Case): O(1)
  • 찾고자 하는 값이 리스트의 첫 번째 요소인 경우.
• 평균 경우 (Average Case): O(n)
  • 찾고자 하는 값이 리스트의 중간에 위치하거나, 리스트에 없는 경우.
• 최악의 경우 (Worst Case): O(n)
  • 찾고자 하는 값이 리스트의 마지막 요소인 경우 또는 리스트에 없는 경우.

공간 복잡도

선형 탐색의 공간 복잡도는 O(1)이다. 이는 알고리즘이 리스트를 순차적으로 탐색하기 위해 추가적인 메모리를 거의 사용하지 않기 때문이다.

def linear_search(arr, target):
    for idx, num in enumerate(arr):
        if num == target:
            return idx

arr = [3, 5, 2, 4, 9]
target = 4
result = linear_search(arr, target)
print(f"Element found at index: {result}")  # Output: Element found at index: 3

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms