[이진탐색] 이진탐색 (1) 순차 탐색

순차 탐색

• 가장 기본적인 탐색 방법
• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용
• 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음
• 예시 소스코드

def sequential_search(n, target, array):
  for i in range(n):
    # 현재의 원소가 찾고자 하는 원소와 동일한 경우
    if array[i] == target:
      return i + 1 # 현재 위치 반환 (현재 인덱스 + 1)

input_data = input().split()
n = int(input_data[0])
target = input_data[1]
array = input().split()

print(sequential_search(n, target, array))

• 입력 & 출력 예시

5 C A B C D E 3

• 데이터의 개수가 N개일 때, 최대 N번의 비교 연산을 수행하므로 순차 탐색의 최악의 경우 시간복잡도는 O(N)