이진 탐색(Binary_search) using python

이진 탐색(Binary_search): 배열 내부의 데이터가 정렬되어 있을 경우, 시작점, 끝점, 중간점 필요

찾으려는 데이터와 중간점(middle)위치에 있는 데이터를 반복적으로 비교

시간복잡도: O(logN)

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)

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