[알고리즘개념] 이진 탐색

순차 탐색

시간복잡도 O(N)

for i in range(n):
    if array[i] == target:
        return i + 1

이진 탐색

데이터가 정렬되어 있을 때, 시간복잡도 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, mid-1)
    else:
        return binary_search(array, target, mid+1, 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