[문제] 선형 탐색 구현하기

 

문제

반복문을 사용해 선형 탐색 함수를 구현해 보세요.

linear_search() 함수는 두 개의 파라미터를 받습니다.

target: 찾고 있는 요소 data: 탐색할 리스트 data에 target 값이 있는 경우 함수는 target 값이 위치한 인덱스를 리턴합니다.

data에 target 값이 없는 경우 None을 리턴합니다.

 

실습해설

선형 탐색은 리스트의 요소들을 앞에서부터 차례대로 비교하면서 찾는 값이 있는지 확인하는 알고리즘입니다.

data 반복하기

아래처럼 for문을 사용하면 data의 요소를 차례로 가져올 수 있는데요.

for element in data:

 

 

여기서 주의해야 할 점은 linear_search() 함수에선 요소 자체가 아니라 요소가 위치한 인덱스를 리턴해야 한다는 겁니다.

요소 자체를 리턴하면 파라미터(target)에서 받은 값을 그대로 리턴하는 거니까 아무런 의미가 없는데요.

위 코드처럼 각 요소의 값을 그대로 가져오는 게 아니라 아래 코드처럼 range() 함수와 인덱스를 사용해서 각 요소에 접근해야 합니다.

for i in range(len(data)):

 

여기서 주의해야 할 점은 linear_search() 함수에선 요소 자체가 아니라 요소가 위치한 인덱스를 리턴해야 한다는 겁니다.

요소 자체를 리턴하면 파라미터(target)에서 받은 값을 그대로 리턴하는 거니까 아무런 의미가 없는데요.

위 코드처럼 각 요소의 값을 그대로 가져오는 게 아니라 아래 코드처럼 range() 함수와 인덱스를 사용해서 각 요소에 접근해야 합니다.

for i in range(len(data)):

 

현재 요소와 target 비교하기

for 반복문 안에서는 현재 요소(data[i])의 값이랑 찾고 있는 요소(target)의 값이 같은지 확인해야 합니다.

만약 두 값이 똑같으면 값을 찾은 거니까 그때의 인덱스 i를 리턴해 주면 됩니다.

for i in range(len(data)):
    if data[i] == target:
        return i

 

target 값이 없으면 None 리턴하기

만약에 for 반복문을 전부 실행했는데도 아무런 값을 리턴하지 않고 반복문을 빠져 나왔다면, data에 target이랑 똑같은 값이 없다는 뜻입니다. 그럼 None을 리턴해 줍니다.

def linear_search(target, data):
    for i in range(len(my_list)):
        if data[i] == target:
            return i
    return None

 

참고로 파이썬에서는 함수가 값을 리턴하지 않고 종료되면 자동으로 None을 리턴하기 때문에 return None은 생략할 수도 있어요.

 

모범답안

def linear_search(target, data):
    for i in range(len(data)):
        if data[i] == target:
            return i

# 테스트 코드
print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

공감과 댓글은 저에게 큰 힘이 됩니다.

 

Starting Google Play App Distribution! "Tester Share" for Recruiting 20 Testers for a Closed Test.

Tester Share [테스터쉐어] - Google Play 앱