Binary Search Binary Search (이진 탐색) 이란 무엇인가?

[김건우]

안녕하세요. 이번 시간에는 이진 탐색에 대해 배워보는 시간을 가져보도록 하겠습니다.

우선 이진 탐색을 배우기 전, 몇 가지 배워야 하는 목록이 존재합니다. 함께 보시도록 하겠습니다.

이진이란?

이진은 2진법, 3진법, 8진법 10진법, 16진법 할 때 사용하는 단어이며, 다양한 방법들중 0과 1 두 개의 숫자를 활용하여 숫자들을 묶는 방법을 말합니다. 

예를 들어서 다음과 같은 숫자들을 2진수라고 부릅니다.

10101

01010

0과 1의 조합으로 숫자를 만드는 것을 의미합니다.

일단 이진이란 개념에 대해서 알게 되었으니, 이진 탐색에 대해 다시 알아보는 시간을 가져보도록 하겠습니다.

이진 탐색이란?

이진 탐색의 개념에 대해 배우기 전 우선 Wikepedia 에서 정의한 뜻을 알아보았습니다.

이처럼, 이진 탐색은 Data 가 정렬되어 있는 List 에서 특정 값, 즉 특정 Element (원소) 를 찾는 Algorithm 기법입니다. 그리고 처음 정렬된 List 을 순회 시, 중간 값을 임의 값으로 선택하여, 그 값과 특정 Element (원소) 의 값의 크고 작음을 비교하는 방식을 채택하고 있습니다.

그렇다면 이진 탐색을 하기 전, 정렬된 List 가 왜 필요할까요?

한 번 예제 코드와 그 과정을 통해 그 이유를 알아보도록 하겠습니다.

우선 전체 코드 중, List 와 Target 값을 정의하였습니다. List 에는 정렬되지 않은 값들이 마구잡이로 배치되어 있고, target 은 List 에서 찾고자 하는 값을 가르키는 코드입니다.

그리고 뒤에서 만들 binary_search_list 함수를 불러와서 찾고자 하는 값이 get_list 안에 존재하는지 그 여부를 확인합니다. 존재한다면 찾고자 하는 값을 불러오고, 존재하지 않다면 "찾으려는 {0} 가 존재하지 않습니다" 와 같이 출력합니다."

정렬되지 않은 List 를 처음 index 와 마지막 index 를 활용하여 찾고자 하는 값이 List 에 존재하는지 여부를 확인하는 코드입니다. 만약 찾고자 하는 값이 중간 값인 mid 보다 클 경우, start 의 값을 1 만큼 증가시키고,  mid 보다 작을 경우, end 의 값을 1만큼 감소시킵니다.

이제 한 번 실행해보도록 하겠습니다.

코드 결과는 하단의 이미지와 같이 출력이 됩니다.

결과가 이상하게 나왔습니다. 우리가 원했던 값은 21 이라는 숫자가 List 에 존재하는지에 대한 여부를 확인하려고 했는데 없다고 뜨네요. 

이처럼 이진 탐색은 List 중간 값에 List 의 중앙 값이 포함되어 있다는 것을 가정하고 작동합니다. 그러나 정렬을 하지 않는다면 List 의 중앙 값이 List 중간 값에 포함되지 않았다는 가정과 같아집니다.

또한 List 의 중앙 값은 List 어디에나 있을 수 있고, List 는 그 중앙 값을 활용하여 찾고자 하는 값을 찾습니다. 그러나 정렬을 하지 않는다면 List 의 잘못된 중앙값을 찾을 것이고, 찾고자 하는 값을 찾지 못하는 상황이 발생할 수 있기 때문에 반드시 정렬을 해야합니다.

코드 수정

하단의 코드와 같이 먼저 List 와 찾고자 하는 값을 준비해줍니다. 그리고 List 를 정렬한 후, 이진 탐색을 진행합니다.

<코드 복사>

def binary_search_list(target, data):

    start = 0

    data.sort()

    end = len(data) - 1

    print(target, data)

    while start <= end:

        mid = (start + end) // 2

        if (data[mid] == target):

            return mid

        elif (data[mid] < target):

            start = mid + 1

        else:

            end = mid - 1

    return None

get_list = [12, 25, 21, 18, 35, 18, 8]

target = 21

get_value = binary_search_list(target, get_list)

if (get_value):  print(get_list[get_value])

else:   print("찾으려는 {0} 가 존재하지 않습니다.".format(target))

이상 이번 시간 포스팅을 마치도록 하겠습니다. 감사합니다.