Binary Search (feat. Binary Search Tree)

Published at

2024/10/17

Last edited time

2024/10/17 10:30

Created

2024/10/17 08:57

Section

Algorithm

Status

Done

Series

From the Bottom

Binary Search (이진 탐색)

개요

이진 탐색(Binary Search)는 절반씩 나누어 가면서 찾아가는 알고리즘이다.

탐색이란?

원하는 데이터를 찾는 작업을 탐색이라고 한다.

다른 말로, 레코드의 집합에서 주어진 키를 지닌 레코드를 찾는 작업을 탐색이라 하며, 이 때 주어진 키를 목표 키 (Target Key), 또는 탐색 (Search Key)라고 부른다. 물론 탐색 키를 지닌 레코드가 하나 이상일 수도 있고 없을 수도 있다. (주우석, 2015)

보통 이미 정렬된 자료에서 탐색을 진행한다고 가정한다. 실제로는 아마 그렇지 않을 경우가 많겠지만 말이다.

자료구조는 정보를 저장하기 위한 것이지만 결국은 저장된 정보를 탐색해야하는 최종 목적이 있고, 어떻게 탐색하느냐에 따라서 성능이 크게 좌우될 수도 있다.

이진 탐색 (Binary Search)

이진 탐색은 정렬된 배열에서 원하는 값을 찾기 위해 사용되는 효율적인 탐색 알고리즘이다. 탐색 범위를 절반으로 줄여가며, 탐색할 데이터의 중간값과 비교하는 방식으로 진행된다.

이때 시간 복잡도는

O(\log⁡n)

으로 매우 효율적이다. 다만, 이 때 데이터들이 정렬되있다는 가정을 한다.

cf) 선형 탐색의 경우

O(n)

의 시간 복잡도를 가짐

이진 탐색의 수도 코드는 다음과 같다.

BinarySearch(arr, first, last, key):
    if first > last:
        return -1  // key를 찾지 못함

    mid = (first + last) // 2

    if arr[mid] == key:
        return mid  // key를 찾음

    else if arr[mid] > key:
        return BinarySearch(arr, first, mid - 1, key)  // 왼쪽 절반을 탐색

    else:
        return BinarySearch(arr, mid + 1, last, key)  // 오른쪽 절반을 탐색
Plain Text
복사

이진 탐색 예시

우리가 정렬된 배열

[1, 3, 5, 7, 9, 11, 13]

에서 숫자 7을 찾고 싶다고 가정하자. 이진 탐색 알고리즘을 사용하여 이 값을 찾아보자.

이진 탐색 과정 (진짜 간단하게)

초기 배열과 목표 값:

배열

[1, 3, 5, 7, 9, 11, 13]

에서 숫자 7을 찾는다.

초기 first는 0, last는 6, key는 7이다.

1단계 (첫 번째 중간 값 확인):

•

중간 인덱스 mid = (0 + 6) // 2 = 3.

•

중간 값은 arr[3] = 7.

•

7 == 7이므로 목표 값을 찾았다.

•

탐색 종료, 인덱스 3에서 목표 값을 찾았다.

•

탐색 과정 설명

배열: [1,3,5,7,9,11,13][1, 3, 5, 7, 9, 11, 13][1,3,5,7,9,11,13]

first = 0, last = 6, mid = 3, arr[mid] = 7

중간 값이 7과 같으므로 탐색 종료.

이진 탐색 코드 (C++)

void BinarySearch(int A[], int First, int Last, int Key, int& Index) {
	if (First > Last) 
		index = -1; 
		
	else {
		int Mid = (First + Last) / 2;
		if (Key == A[Mid]) {
			Index = Mid;
			else if (Key < A[Mid]) BinarySearch(A, First, Mid-1, Key, Index);
			
			else
				BinarySearch(A, Mid+1, Last, Key, Index);
		}
	}
}
C++
복사

이진 탐색 코드 (Python)

def binary_search(arr, first, last, key):
    if first > last:
        return -1
    mid = (first + last) // 2
    if arr[mid] == key:
        return mid
    elif arr[mid] > key:
        return binary_search(arr, first, mid - 1, key)
    else:
        return binary_search(arr, mid + 1, last, key)

# Example usage:
arr = [2, 3, 5, 7, 11, 13, 17]
key = 7
index = binary_search(arr, 0, len(arr) - 1, key)
print(f"Key found at index: {index}")
Python
복사

Binary Search Tree (이진 탐색 트리, BST)

사실 이 부분을 따로 한 부분으로 해야할까 싶었으나, 이진 탐색을 배우면서 한 번에 쓰는게 낫겠다 싶어서 이렇게 쓴다.

트리 구조는 이미 다룬바가 있어 설명은 하지 않겠으나, 이진 탐색이 앞에 붙으므로 관련된 내용을 설명해보고자 한다.

BST는 이진 탐색 알고리즘의 원리를 트리 자료구조에 적용한 것이다. 각 노드는 왼쪽 자식은 자신보다 작은 값을, 오른쪽 자식은 자신보다 큰 값을 가진다는 규칙을 따르고 있다. (정렬된 데이터를 기반으로 했을 때)

이진 탐색 트리의 효율은 트리 모습에 좌우되며 최악의 경우 검색 효율은

O(logN)

이다 (주우석, 2015)

이는 트리의 높이가 lgN 의 형태를 띄기 때문에, 트리의 높이가 높을 수록 성능이 안좋아지는 것이다. 만약 트리의 높이가 엄청 높은, 가령 연결리스트에 가까운 트리라면 검색 효율은

O(N)

에 접근한다.

AVL 트리나, 레드-블랙 트리 같은 균형 트리(Balanced Tree) 가 존재하는 것은 바로 이유에 근거한다. 균형이 잡혀야 탐색에 유리하기 때문이다.

이진 탐색 트리를 구현한 코드는 다음과 같다.

이진 탐색 트리 구현 (Python)

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BinarySearchTree:
    def __init__(self):
        self.root = None

    # 삽입 메서드
    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert(self.root, key)

    def _insert(self, current_node, key):
        if key < current_node.val:
            if current_node.left is None:
                current_node.left = Node(key)
            else:
                self._insert(current_node.left, key)
        else:
            if current_node.right is None:
                current_node.right = Node(key)
            else:
                self._insert(current_node.right, key)

    # 탐색 메서드
    def search(self, key):
        return self._search(self.root, key)

    def _search(self, current_node, key):
        if current_node is None or current_node.val == key:
            return current_node

        if key < current_node.val:
            return self._search(current_node.left, key)
        return self._search(current_node.right, key)

    # 삭제 메서드
    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, current_node, key):
        if current_node is None:
            return current_node

        if key < current_node.val:
            current_node.left = self._delete(current_node.left, key)
        elif key > current_node.val:
            current_node.right = self._delete(current_node.right, key)
        else:
            # 노드가 하나 이하의 자식을 가질 경우
            if current_node.left is None:
                return current_node.right
            elif current_node.right is None:
                return current_node.left

            # 노드가 두 개의 자식을 가질 경우
            temp_val = self._min_value_node(current_node.right)
            current_node.val = temp_val.val
            current_node.right = self._delete(current_node.right, temp_val.val)

        return current_node

    # 최소값 찾는 메서드 (삭제 시 필요)
    def _min_value_node(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current

    # 중위 순회 (Inorder Traversal)
    def inorder(self):
        self._inorder(self.root)

    def _inorder(self, node):
        if node is not None:
            self._inorder(node.left)
            print(node.val, end=' ')
            self._inorder(node.right)
Python
복사

기능 설명

삽입 (insert):

•

트리에서 적절한 위치를 찾아 새로운 값을 삽입한다.

•

삽입할 값이 현재 노드보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 이동하여 노드를 삽입한다.

탐색 (search):

•

주어진 값을 트리에서 찾아 반환한다.

•

현재 노드와 값을 비교하여 왼쪽 또는 오른쪽 서브트리로 이동한다.

삭제 (delete):

•

트리에서 노드를 삭제한다. 이 때 삭제할 노드의 자식 노드에 따라 다르게 처리해야만 한다.

◦

자식이 없거나 하나인 경우 간단히 제거하고, 자식이 두 개인 경우 오른쪽 서브트리에서 가장 작은 값을 찾아 대체한다.

중위 순회 (inorder):

•

트리의 모든 노드를 정렬된 순서로 출력한다.

•

중위 순회는 왼쪽 서브트리 -> 현재 노드 -> 오른쪽 서브트리 순으로 순회.

사용 예시

# 이진 탐색 트리 생성
bst = BinarySearchTree()

# 노드 삽입
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
bst.insert(80)

# 트리 출력 (중위 순회)
print("Inorder traversal of the tree:")
bst.inorder()

# 값 탐색
key = 60
if bst.search(key):
    print(f"\\nKey {key} found in the tree.")
else:
    print(f"\\nKey {key} not found in the tree.")

# 값 삭제
bst.delete(70)
print("\\nInorder traversal after deleting 70:")
bst.inorder()
Python
복사

BST와 연결리스트 비교 표

구조	연산	최악의 경우 시간 복잡도	평균적인 경우 시간 복잡도
정렬된 배열	탐색	$O(\log n)$ (이진탐색)	$O(\log n)$
	삽입	$O(n)$	$O(n)$
	삭제	$O(n)$	$O(n)$
정렬되지 않은 연결 리스트	탐색	$O(n)$	$O(n)$
	삽입	$O(1)$ (리스트 끝에 삽입)	$O(1)$
	삭제	O(n) (탐색 후 삭제)	$O(n)$
이진 탐색 트리 (BST)	탐색	$O(n)$ (비균형)	$O(\log n)$
	삽입	$O(n)$ (비균형)	$O(\log n)$
	삭제	$O(n)$ (비균형)	$O(\log n)$

요약

이진 탐색은 정렬된 배열에서 중간값을 반복적으로 비교해 빠르게 값을 찾는 알고리즘이다. 시간 복잡도는 O(log⁡n)O(\log n)O(logn)

이진 탐색 트리 (BST)는 각 노드가 왼쪽 자식보다 크고, 오른쪽 자식보다 작은 값을 가지는 트리로, 균형이 중요하다.

REFERENCES

주우석, 2015, C/C++로 배우는 자료구조론, 한빛미디어

Written by Changyu Lee