[알고리즘] 이진 탐색(Binary Search)

이진 탐색에 들어가기 앞서, 순차 탐색과 무엇이 다른지 확인해보겠습니다.

 

순차 탐색(Sequential Search)

 

순차 탐색

출처 : https://velog.io/@yujo/JS%EC%84%A0%ED%98%95-%ED%83%90%EC%83%89Linear-Search

 

 

특징

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 데이터가 정렬되어 있지 않아도 사용 가능
• 최악의 경우 시간복잡도 O(N)

코드

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


print('생성할 원소 개수를 입력한 뒤 찾을 문자열 입력')
n, target = input().split()
n = int(n)

print("문자열 입력")
arr = input().split()

print(sequential_search(n,target,arr))

순차탐색의 한계

순차탐색의 치명적인 문제는 최악의 시간복잡도가 O(N)이 걸려 시간이 오래 걸리는 단점이 있습니다. 이를 해결하기 위한 탐색 방법이 이진 탐색(Binary Search)입니다. 이진 탐색을 이해하기 위해서는 트리 자료구조에 대하여 알아야 합니다.

 

트리 자료구조

트리구조

출처 : 'https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c'

특징

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

 

이진 트리 (Binary Tree)

특징

• 트리구조 중 자식 노드가 최대 2개인 트리
• 부모 노드보다 왼쪽 자식 노드가 작다
• 부모 노드보다 오른쪽 자식 노드가 크다

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

이진 탐색(Binary Search): 반으로 쪼개면서 탐색

이진 탐색

출처 : https://blog.penjee.com/5-gifs-to-understand-binary-search-tree

특징

•  배열 내부의 데이터가 정렬되어 있을 때만 사용 가능한 알고리즘
• 사용하는 변수 : 시작점, 끝점, 중간점
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 데이터를 찾음
• 최악의 경우 시간 복잡도 - 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,end-1)
    else:
        return binary_search(array,target,mid+1,end)

n, target = map(int,input().split())
arr = list(map(int,input().split()))
result = binary_search(arr,target,0,n-1)
if result == None:
    print("존재 X")
else:
    print(result+1)

반복문

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 = map(int,input().split())
arr = list(map(int,input().split()))
result = binary_search(arr,target,0,n-1)
if result == None:
    print("존재 X")
else:
    print(result+1)

빠르게 입력 받기

데이터의 개수가 많은 문제에 input() 함수를 사용하면 동작 속도가 느리므로
sys 라이브러리의 readline()함수 이용

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

 

 

 

출처

 

이것이 취업을 위한 코딩 테스트다 with 파이썬