이진탐색(Binary Search)는 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 이미 정렬되어있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.
이진탐색은 위치를 나타내는 변수 3개 시작점, 끝점, 중간점을 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다.
이진탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다. 이진탐색을 구현하는 방법으로는 재귀 함수와 반복문을 이용한 2가지 방법이 있다.
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
# 찾은 경우 중간점 index return
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 = 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)
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
# 찾은 경우 index return
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return None
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)
데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어있다. 그래서 이진 탐색과 유사한 방법을 이용해서 데이터를 빠르게 탐색할 수 있다. 트리 자료구조는 노드와 노드의 연결료 표현한다. 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다. 트리 구조는 다음과 같은 특징이 있다.
트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다. 이진 탐색 트리는 이진 탐색이 동작할 수 있도록 만들어진 효율적 탐색이 가능한 자료구조이다. 이진 탐색 트리는 다음과 같은 특징을 가진다.
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립해야 이진 탐색트리 이다.
이것이 코딩테스트다 with python