이진 탐색 Binary Search (Python)

 이진 탐색은 이미 순서대로 정렬된 arr에서, 특정 값을 보다 빠르게 찾기 위해서 사용되는 방법이다. 처음부터 차례대로 탐색하는 순차탐색 O(N) 과 다르게, 중앙값 mid 를 기준으로 나눈 arr에서 target이 앞/뒤 중 어디에 위치하는지를 찾는다. 이진 탐색의 시간 복잡도는 O(log N) 으로, 보다 빠른 탐색이 필요한 PS에서 유용한 라이브러리로 사용할 수 있다.

 이진 탐색 함수를 짤 때 두 가지 방법으로 짤 수 있다. 하나는 재귀적으로, 남은 하나는 반복적으로 짜는 방법이다.

 간단하게 PS 용으로 쓰기 위해서는 반복적인 방법을 주로 사용한다. 코드 짜기 쉽고, Python의 재귀 깊이를 고려하지 않기 위함이다.

 또한, 이진 탐색 코드를 짤 때 주의할 점이 있다.

 (1) 탐색을 진행할 arr가 이미 정렬되어있어야 한다.
 (2) start, end, mid가 바뀌는 조건을 주의해야 한다.
     - 특히, 반복적 방법으로 while 사용 할 때, 반복 마다 start, end, mid가 바뀌는지, 오류 없는지 체크해야 함
 (3) 반복적 방법에서는 무한루프 주의, 재귀 방법에서는 return 값 주의하기

 아래에서 코드를 확인할 수 있으나, 되도록이면 직접 구현하는 연습을 하자.

def BinarySearch(arr, target):
    mid = len(arr) // 2
    start = 0
    end = len(arr) - 1

    while start <= end:
        mid = (start + end) // 2
        if target == arr[mid]:
            return mid
        elif target < arr[mid]:
            end = mid - 1
        else:
            start = mid + 1