이진 탐색 알고리즘

이진 탐색(Binary Search)

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 

시간 복잡도는 $O(logn)$을 가진다.

 

 

✔ 이진 탐색 과정

1. 데이터 집합(배열)의 중앙 요소를 선택합니다.   

• 중간값 : 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눈다.

 

여기서 target = 9 로 한다.

 

 

2. 중앙 요소의 값과 찾으려는 값을 서로 비교한다.

 

    만약 찾으려는 값이 중앙 요소의 값보다 작다면 중앙 요소의 왼편에서 중앙 요소를 다시 택하고,

    반대로 찾으려는 값이 중앙 요소의 값보다 크다면 오른편에서 중앙 요소를 다시 택하게 됩니다.

 

•  중앙값의 7과 비교하여 9가 더 크기 때문에 왼쪽을 지우고 오른쪽에서 중앙값을 구한다.
•  다시 구한 중앙값은 10이다.

 

3. 위의 2번을 반복하여 값을 찾아준다.

• 위의 중앙값은 10으로 target 보다 크므로 오른쪽을 버리고 왼쪽을 탐색한다.
• 다음에 중앙을 구하면 9가되고 target값과 같아지므로 종료된다.

 

 

✔ 코드

• 반복문을 이용해서 구현

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

 

• 재귀함수를 이용해서 구현

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)

 

 

---

이진 탐색 트리

이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조이다.

이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안되었다.

 

• 부모 노드보다 왼쪽 자식 노드가 작다
• 부모 노드보다 오른쪽 자식 노드가 크다 .
• 중복된 노드가 없어야 한다.
• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.

이진탐색트리를 순회할 때는 중위순회(inorder) 방식을 사용한다. (왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회)

이렇게 하면 이진탐색트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있다. 

 

순회 :  1 - 3 - 4 - 6 - 7 - 8 - 10 - 13 - 14

 

✔ 코드

class Node(object):
    def __init__(self, data):
    self.data = data
    self.left = self.right = None

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

    #삽입
    def insert(self, data):
        self.root = self._insert_value(self.root, data)
        return self.root is not None
    def _insert_value(self, node, data):
        if node is None:
            node = Node(data)
        else:
            if data <= node.data:
                node.left = self._insert_value(node.left, data)
            else:
                node.right = self._insert_value(node.right, data)
        return node
    
    #탐색
    def find(self, key):
        return self._find_value(self.root, key)
    
    def _find_value(self, root, key):
        if root is None or root.data == key:
            return root is not None
        elif key < root.data:
            return self._find_value(root.left, key)
        else:
            return self._find_value(root.right, key)

    #삭제
    def delete(self, key):
        self.root, deleted = self._delete_value(self.root, key)
        return deleted
    def _delete_value(self, node, key):
        if node is None:
            return node, False
        
        deleted = False
        if key == node.data:
            deleted = True
            if node.left and node.right:
                # replace the node to the leftmost of node.right
                parent, child = node, node.right
                while child.left is not None:
                    parent, child = child, child.left
                child.left = node.left
                if parent != node:
                    parent.left = child.right
                    child.right = node.right
                node = child
            elif node.left or node.right:
                node = node.left or node.right
            else:
                node = None
        elif key < node.data:
            node.left, deleted = self._delete_value(node.left, key)
        else:
            node.right, deleted = self._delete_value(node.right, key)
        return node, deleted