[문제] 이진 탐색 구현하기

 

문제

반복문을 사용해 이진 탐색 함수를 구현하세요.

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

• target: 찾고 있는 요소
• data: 탐색할 리스트

data에 target 값이 있는 경우 함수는 target 값이 위치한 인덱스를 리턴합니다.

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

 

실습 해설

이진 탐색은 요소를 찾을 때까지 반복해서 범위를 반으로 줄이면서 원하는 값을 찾는 알고리즘입니다.

이때 범위를 나누는 기준은 찾는 값과 가운데 있는 값을 비교했을 때 작냐 크냐인데요.

만약 찾는 값이 더 작다면 탐색 범위를 왼쪽 절반으로 줄이고, 더 크다면 탐색 범위를 오른쪽 절반으로 줄입니다.

만약 같은 값이라면 가운데 있는 그 값이 우리가 찾는 요소이죠.

 

검색 범위 정의하기

이진 탐색에서는 탐색하는 동안 반복해서 범위가 절반으로 줄어듭니다.

그래서 탐색 범위를 나타낼 변수가 필요한데요, 현재 탐색 범위의 왼쪽이랑 오른쪽 인덱스를 변수로 저장해서 각 반복에 대한 검색 범위를 추적할 수 있습니다.

left_index, right_index 변수를 만들 건데요.

처음엔 검색 범위가 리스트 전체죠?

리스트 전체의 가장 왼쪽 인덱스와 가장 오른쪽 인덱스는 각각 0이랑 len(data) - 1로 값을 저장해 줄게요.

앞으로 반복문에서 left_index 값을 키우거나 right_index 값을 줄이면서 탐색할 범위를 줄여 나가면 됩니다.

def binary_search(target, data):
    left_index, right_index = 0, len(data) - 1

 

반복문의 조건 작성하기

반복문 안에서는 중간 값을 target의 값이랑 비교하고 탐색할 범위를 반으로 줄여야 합니다.

이때 범위가 줄어드는 방향은 일정하지 않으니까 for문보다 while문을 사용하는게 더 좋습니다.

while문의 조건은 어떻게 될까요? 아래 조건 중 하나가 충족됐을 때 반복문을 종료하면 되는데요.

1. target을 찾은 경우(탐색 범위의 중앙에 있는 값이 target 값인 경우)
2. data에 target 값이 존재하지 않는다고 확신할 수 있는 경우

target을 찾으면 인덱스를 바로 리턴할 수 있는데요.

이때 함수는 자동으로 종료되니까 굳이 while문에서 1번 조건을 확인하지 않아도 됩니다.

그러면 2번 조건을 어떻게 쓰면 될까요? 탐색 범위가 완전히 줄어들어서 범위 안에 요소가 하나도 없다면 data에 target이 존재하지 않는다고 확신할 수 있습니다.

범위가 완전히 줄어들었다는 건 left_index가 right_index보다 커진 경우인데요.

그래서 left_index가 right_index보다 작거나 같은 동안에는 탐색을 계속 진행합니다.

이걸 while 반복문의 조건으로 써 주면 되겠네요.

def binary_search(target, data):
    left_index, right_index = 0, len(data) - 1

    while left_index <= right_index:

 

중간 요소 찾기

반복문 안에 코드를 써 볼게요. 반복할 때마다 target 값이랑 현재 탐색 범위의 중간 값을 비교하는데요.

일단 먼저 중간 인덱스(mid_index)를 계산해서 중간에 있는 요소(mid_element)를 가져오는 코드를 써 볼게요.

while left_index <= right_index:
    mid_index = (left_index + right_index) // 2
    mid_element = data[mid_index]

이때 홀수를 2로 나누면 3.5 같이 정수가 아닌 숫자가 나올 수 있으니까 정수로 만들어 주기 위해서 // 연산을 사용했습니다.

탐색 범위의 요소가 짝수 개라면 한가운데에서 왼쪽 인덱스를 선택하고, 홀수 개라면 한가운데 있는 인덱스를 선택하는 거예요.

 

target이랑 mid_element 비교하기

값을 비교하고 탐색 범위를 줄여 봅시다.

target과  mid_element를 비교해 줄게요.

while left_index <= right_index:
    mid_index = (left_index + right_index) // 2
    mid_element = data[mid_index]

    if target == mid_element:
        # 어떤 작업을 하면 될까요?
    elif target < mid_element:
        # 어떤 작업을 하면 될까요?
    elif target > mid_element:
        # 어떤 작업을 하면 될까요?

가장 쉬운 경우는 값이 같아서 원하는 요소를 찾은 경우입니다.

요소를 찾았다면 인덱스 값인 mid_index를 리턴해 주면 됩니다.

if target == mid_element:
    return mid_index

target이 mid_element보다 작다면 범위를 왼쪽으로 줄여야겠죠.

right_index를 현재 가운데 인덱스인 mid_index의 바로 왼쪽으로 옮겨서 현재 탐색 범위의 오른쪽 절반을 제거해 줍니다.

elif target < mid_element:
    right_index = mid_index - 1

target이 mid_element보다 크다면 반대로 범위를 오른쪽으로 줄여야겠죠?

left_index를 현재 가운데 인덱스인 mid_index의 바로 오른쪽으로 옮겨서 현재 탐색 범위의 왼쪽 절반을 제거해 줍니다.

elif target > mid_element:
    left_index = mid_index + 1

target이 없는 경우

만약 아무 것도 리턴하지 않고 while문이 종료된다면 data에 target이 없다는 의미죠?

이럴 땐 None을 리턴해야 하는데요, 함수의 마지막에 return None을 써 줘도 되지만 파이썬에서 함수는 기본적으로 아무 것도 리턴하지 않으면 None을 리턴하기 때문에 생략해 줘도 됩니다.

모범 답안

def binary_search(target, data):
    left_index, right_index = 0, len(data) - 1

    while left_index <= right_index:
        mid_index = (left_index + right_index) // 2
        mid_element = data[mid_index]

        if target == mid_element:
            return mid_index
        elif target < mid_element:
            right_index = mid_index - 1
        elif target > mid_element:
            left_index = mid_index + 1

# 테스트 코드
print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_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 앱