[Algorithm] Binary Search

Binary Search

---

Sequential Search

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

def sequential_search(n, target, array):
    for i in range(n):
        if array[i] == target:
            return i + 1

순차 탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 하므로 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하다.

따라서 순차 탐색의 시간 복잡도는 \(O(N)\)이다.

 

Binary Search

이진 탐색은 데이터가 정렬되어 있어야만 사용할 수 있으며, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.

• 시작점
• 끝점
• 중간점

이진 탐색은 위치를 나타내는 3개의 변수를 사용하며, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는다.

이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 \(O(logN)\)이다.

 

재귀 함수로 구현

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)

반복문으로 구현

  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

 

Tree

트리 자료구조는 노드와 노드의 연결로 표현된 그래프 자료구조의 일종으로, 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용한다.

Tree의 특징

• 트리는 부모 노드와 자식 노드의 관계로 표현된다.
• 트리의 최상단 노드를 루트 노드라고 한다.
• 트리의 최하단 노드를 단말 노드라고 한다.
• 트리에서 일부를 떼어내도 트리 구조이며, 이를 서브 트리라고 한다.
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

 

Binary Search Tree

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립하는 트리로 효율적인 탐색이 가능하다.

 

데이터 입력

이진 탐색 문제는 입력 데이터가 많거나 탐색 범위가 매우 넓은 편으로, 데이터를 입력받을 때 input() 함수를 사용하면 시간 초과가 발생할 수 있다.

입력 데이터가 많을 경우에는 sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있다.

import sys
input_data = sys.stdin.readline().rstrip()

sys 라이브러리를 사용할 때는 한 줄을 입력받고 나서 rstrip() 함수를 꼭 호출해야 한다.

readline()으로 입력하면 엔터가 줄 바꿈 기호로 입력되어 이 공백 문자를 제거하기 위함이다.