이진탐색

전제조건 : 리스트가 오름차순으로 정렬되어 있어야 한다.
복잡도 : O(log2(N))

import random

data = random.sample(range(1,100), random.randint(10,20))
data.sort()
print(data)

target = int(input('search number : '))


start = 0
end = len(data) - 1

while start <= end:
    mid = (start + end) // 2

    if data[mid] == target:
        break
    elif data[mid] < target:
        start = mid + 1
    else:
        end = mid -1


print(f'searchResultIdx: {mid}')

*재귀적 구현

# data는 오름차순으로 정렬된 리스트
def binary_search_recursion(target, start, end, data):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1        

    return binary_search_recursion(target, start, end, data)