범위를 좁혀가는 탐색

가장 기본 탐색인 "순차 탐색"을 알아보자

 

순차 탐색이란 '리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법'

1) 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용

2) 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있는 장점이 있음

 

순차 탐색의 구조를 보자

a b c d e 중 c 를 찾아보는 예이다

 

step0) 초기 단계

a b c d e 

 

step1) 가장 먼저 첫 번째 데이터를 확인 한다. a 는 찾고자 하는 문자열과 같지않다. 따라서 다음 데이터로 이동한다.

a b c d e 

 

step2) 두 번째 데이터를 확인한다. b 또한 찾고자 하는 문자열과 같지 않다. 다음 데이터로 이동한다.

a b c d e 

 

step2) 세 번째 데이터를 확인한다. c 는 찾고자 하는 문자열과 같다. 다음 탐색을 마친다.

a b c d e 

 

순차 탐색은 이름처럼 순차로 데이터를 탐색한다. 

리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하는 것이다.

 

다음은 순차 탐색 소스코드 예시이다.

 

# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
    # 각 원소를 하나씩 확인하며
    for i in range(n):
        # 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i] == target:
            return i + 1 # 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기)
    return -1 # 원소를 찾지 못한 경우 -1 반환

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))

 

순차 탐색의 경우 하나하나씩 확인해가며 원하는 target을 찾는 것이다.

함수를 통해 원하는 target을 발견하고 인덱스(i +1)를 반환한다.

이해에는 큰 어려움이 없었다.  

 

 

<출처> 이것이 코딩 테스트다 (나동빈 지음)