순차 탐색

순차 탐색(Sequential Search)은 가장 기본적인 검색 알고리즘이다. 데이터가 정렬되어 있지 않거나 아무런 정보가 없을 때 주로 사용된다. 이 방법은 리스트의 각 요소를 하나씩 차례대로 접근하여 찾고자 하는 값을 비교한다.

동작 원리

1. 리스트의 첫 번째 요소부터 시작하여 찾고자 하는 값과 비교한다.
2. 일치하는 값을 찾을 때까지 리스트의 모든 요소를 순차적으로 검사한다.
3. 값이 일치하면 해당 요소의 위치(index)를 반환한다.
4. 리스트의 끝까지 검사했는데도 찾고자 하는 값이 없으면, 해당 값이 리스트에 없다고 반환한다.

순차 탐색의 특징

• 데이터의 정렬 여부와 관계없이 사용할 수 있다.
• 평균적으로 데이터의 절반까지 검사해야 하므로 $O(n)$의 시간 복잡도를 갖는다.
• 데이터셋이 크면 클수록 비효율적이다.

Python 코드

def sequential_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i  # 찾은 값의 인덱스 반환
    return -1  # 리스트 내에 찾는 값이 없을 경우 -1 반환

예제

data = [3, 4, 1, 5, 9, 2, 8, 6, 7]
result = sequential_search(data, 5)
if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found in the list")

이 코드는 5라는 값을 리스트에서 찾으려고 시도하고, 해당 값의 인덱스를 출력하거나 리스트 내에 값이 없을 경우 메시지를 출력한다.