이진 탐색(Binary Search) 이란?

Tabber·2021년 5월 31일
2

알고리즘

목록 보기
1/4
post-thumbnail

참고출처 - 나동빈님 Github (https://github.com/ndb796/python-for-coding-test)

리스트 안에 있는 데이터를 찾기위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

def sequential_search(n, target, array):
    for i in range(n):
        if array[i] == target:
            return i + 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))

위 코드는 순차탐색 알고리즘을 적용해 원하는 문자열을 찾는 프로그램이다.
말 그대로 처음부터 끝까지 하나씩 탐색을 하는 알고리즘이라 최악의 경우 시간 복잡도가 O(N) 이다.


이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬이 되어있다면 매우 빠르게 데이터를 찾을 수 있는 알고리즘이다.

이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 시작점, 끝점, 그리고 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다.

아래의 예시를 같이 보자. 예시는 정렬된 10개의 원소 중 값이 4인 원소를 찾는 과정이다.

1번째

시작점끝점을 각각 정하고, 둘 사이의 중간점을 구한다. 위 배열의 정확한 중간점은 4.5 이지만, 소수점 이하의 수를 버리고 4로 선택했다. 다음으로 우리가 찾으려는 원소인 4의 값과 중간점의 값을 비교한다. 중간점의 데이터인 8이 더 크므로 중간점 뒤에 값들은 확인할 필요가 없다. 따라서 끝점을 [4]의 이전인 [3]으로 옮긴다.

2번째


시작점은 [0], 끝점은 [3], 중간점은 두 수 사이인 [1]을 선택했다.(이 수도 1.5가 정확하지만 소수점 이하 자리를 없앴다) 중간점과 찾으려는 원소인 4를 비교하면 4가 더 크기 때문에 중간점 이하의 수를 볼 필요가 없으니 [1]의 중간점을 [2]로 옮긴다.

3번째

시작점은[2],끝점은[3], 중간점은[2] 이다. 중간점에 위치한 데이터 4는 찾으려는 원소와 동일하므로 이 시점에서 탐색을 종료한다.

위 예시의 전체 원소는 10개지만, 이진 탐색을 통해 단 3번만에 원소의 위치를 찾을 수 있었다.
이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다.

이진탐색을 구현하는 방법에는 재귀함수와, 반복문을 이용하는 방법 2가지가 존재한다.

재귀함수를 이용한 코드

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start+end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target :
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid+1, end)

# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n,target = list(map(int,input().split()))
# 전체 원소 입력받기
array = list(map(int,input().split()))

# 이진 탐색 수행결과
result = binary_search(array,target,0,n-1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result+1)

mid = (start+end) // 2 계산을 이용해 중간점을 계속해서 구해준다.

반복문을 이용한 코드

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end) // 2
        
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

n,target = list(map(int,input().split()))
array = list(map(int,input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result+1)

로직은 똑같고 단순히 재귀로 돌리던걸 반복문을 처리한 것 밖에 없다.


이진 탐색 트리 (Binary Search Tree)

트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다. 이진 탐색 트리란 이진 탐색이 동작할 수 있도록 만들어진 자료구조이다.


보통 이진 탐색 트리는 이 그림과 같은데, 모든 트리가 다 이진 탐색 트리는 아니다. 이진 탐색 드리는 다음과 같은 특징을 가진다.

  • 부모 노드보다 왼쪽 자식 노드가 작다.
  • 부모 노드보다 오른쪽 자식 노드가 크다.

위 특징을 그림을 보고 다시 생각해보자.

도식화 해서 표현하면 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 가 성립해야 이진 탐색 트리라고 할 수 있다. 위 그림이 성립을 한다는 것을 알 수 있다.

이번에는 이진 탐색 트리가 미리 구현되어있다고 가정하고 데이터를 조회하는 과정을 살펴보자. 우리가 찾는 원소는 37이다.

1 번째


아까 봤던 공식대로 37을 찾는 모습이다. 왼쪽의 자식 노드가 부모노드보다 작은걸 확인하고 왼쪽의 모든 수를 확인하지 않는다. 그리고 오른쪽 자식 노드로 37을 찾기 시작한다.

2 번째

왼쪽 자식 노드와 원래의 부모노드를 지나치고, 오른쪽 자식 노드였던 '48'이 이번엔 부모 노드이다. '48'은 우리가 찾는 '37'보다 크다. 공식에 따라 생각을 하면 왼쪽 자식 노드로 가야한다. 오른쪽 자식 노드는 확인할 필요가 없다.

3 번째


현재 방문한 노드의 값인 '37'과 우리가 찾는 수인 '37'이 동일하다. 탐색을 마친다.


마치며

오늘은 이진 탐색의 성질과 알고리즘 코드, 이진 탐색 트리를 알아보았다.

profile
iOS 정복중인 Tabber 입니다.

0개의 댓글