#09 이진 탐색

정렬된 리스트에서 특정 값을 탐색할 때 순차 탐색보다 빠르게 탐색할 수 있는 알고리즘

순차 탐색 : O(n)

이진 탐색 : O(logn)

 

'''
1. start가 end보다 크다면 stop
2. mid 값을 정함
3. mid 인덱스의 값과 target이 같으면 return
4. mid 인덱스의 값보다 target이 작으면 mid 왼쪽에 있으므로 end 값을 mid -1
5. mid 인덱스의 값보다 target이 크면 mid 오른쪽에 있으므로 start 값을 mid + 1 
'''
def binary_search(arr, start, end, target):
    if start > end:
        return None
    mid = (start + end)//2
    if arr[mid] == target:
        return mid
    if arr[mid] > target:
        return binary_search(arr, start, mid-1, target)
    else :
        return binary_search(arr, mid + 1, end, target)

def binary_search_loop(arr, start, end, target):
    while start >= end:
        mid = (start+end)//2
        if arr[mid] == target:
            return mid
        if arr[mid] > target:
            end = mid - 1 
        else:
            start = mid + 1
    return None