이진탐색

이진 탐색 배경

배열(또는 리스트) 내부의 데이터를 일일이 하나씩 탐색해나가면 최악의 경우 데이터 개수가 N개라고 할 때, O(N) 이라는 시간이 든다.

이에 효율적으로 시간을 줄이자는 방법으로 나온 것이 이진 탐색 이다.

이진 탐색이란?

탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

한 번 값의 크기를 비교할 때마다 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도는 O(log2N)

이진 탐색 조건

•

데이터가 크기 순서로 정렬되어 있어야 함

•

시작점, 끝점, 중간점 을 활용한다.

•

찾으려는 값과 중간점의 크기를 반복적으로 비교해가면서 탐색의 범위를 좁혀나간다.

•

중간점(위치)이 실수일 경우, 소수점 아래는 버린다. (int() / // ) 

이진 탐색 코드

이진 탐색은 재귀 함수 , 반복문을 사용하는 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)



# 원소의 개수와 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)
Python
복사

단순 반복문

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 # start > end인 경우에는 None


# 원소의 개수와 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)
Python
복사

이진 탐색 트리

트리 자료구조 중에서 가장 간단한 형태다.

즉, 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다.

이진 탐색 트리는 다음과 같은 특징을 가진다.

•

부모 노드보다 왼쪽 자식 노드가 작다.

•

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

즉, 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 가 만족해야 한다.

이진 탐색 트리에 데이터를 넣고 빼는 방법은 알고리즘보다는 자료구조에 가깝고, 출제 빈도가 낮아서 구현하는 방법을 따로 공부할 필요는 없다.

단, 이진 탐색 트리의 구조가 이미 만들어졌다고 가정하고, 이진 탐색 트리에서 데이터를 조회하는 과정을 살펴보자.

다음은 찾는 원소가 37일때, 동작하는 과정이다.

이진 탐색은 루트 노드부터 방문한다. 루트 노드는 30이고, 찾는 값은 37인데 왼쪽 자식 노드는 30이하이므로 왼쪽은 볼 필요가 없다.  따라서 오른쪽 자식 노드를 방문한다.

오른쪽 자식 노드 48이 이번에는 부모 노드다. 48은 찾는 값 37보다 크다. 앞선 공식에 따라 오른쪽 자식 노드는 모두 48 이상이므로 확인할 필요가 없다. 따라서 왼쪽 노드를 방문한다. 

현재 방문한 노드의 값인 37은 내가 찾는 37과 동일하다. 탐색을 마친다.

자식 노드가 없을 때까지 원소를 찾지 못한다면, 이진 탐색 트리에 해당 원소가 없는 것이다.

빠르게 입력 받기

이진 탐색 문제는 입력 데이터가 많거나 , 탐색 범위가 매우 넓은 편이다.

예를 들어 입력 데이터의 개수가 1000만개를 넘거나 탐색 범위의 크기가 1000억 이상이라면 이진 탐색 알고리즘을 의심해봐야 한다.

이럴 경우 입력 받을 때 sys라이브러리의 readline() 함수를 이용하자!

import sys

input_data = sys.stdin.readline().rstrip() # 개행 문자 제거
Python
복사