이진탐색 알고리즘 (Python)

이진 탐색

---

이진탐색 jpg

 

 

개념

- 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다.

- 데이터가 정렬되어 있어야 사용할 수 있다.

- #시작점 #끝점 #중간점

- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

- 시간 복잡도 : O(logN) 

- 연산 횟수가 매번 감소하기 때문에 입력 데이터가 매우 많거나 탐색 범위가 매우 넓을 때 사용한다.

- sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있다.

import sys
# 하나의 문자열 데이터 입력받기
# 한 줄 입력받고 나서 꼭 rstrip()으로 함수를 호출해야 공백문자를 제거할 수 있다.
input_data = sys.stdin.readline().rstrip()

print(input_data)

 

 

소스코드

1) 재귀 함수로 구현

# 이진 탐색 소스코드(재귀 함수)
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)

# n : 원소의 개수, target : 목표 값
n = 10
target = 7

# array : 전체 원소
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

result = binary_search(array, target, 0, n - 1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

# 출력 결과 : 4

 

2) 반복문으로 구현

# 이진 탐색 소스코드(반복문)
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 : 목표 값
n = 10
target = 7

# array : 전체 원소
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

result = binary_search(array, target, 0, n - 1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

# 출력 결과 : 4

 

이진 탐색 트리

---

이진 탐색 트리 jpg

 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 가 성립하는 트리이다.