Binary Search

Binary Search

오름차순으로 정렬되어있는 리스트 내에서 특정한 값의 인덱스를 찾는 알고리즘입니다.

정렬된 리스트에서만 사용되기에 빠른 속도이고 시간복잡도는 O(logN)입니다.

n/2 혹은 (n+1)/2 번째를 기준으로 좌우를 비교하면서 원하는 값을 찾는 방식입니다.

*예제(flow)

code

def binary_search(arr, target): #이진탐색 함수, target는 찾아야하느 값
    l = 0 #처음엔 0으로 초기화 l은 list의 약자입니다.
    r = len(arr) - 1 #배열의 총 길이에서 하나를 뺀 값이 r (짝수화)

    while l <= r: #l > r이되면 while문 종료로 그 전까지 계속 진행
        m = (l + r) // 2 #이진탐색이 절반의 위치를 구하는 방식이므로 그 방식을 수식화
        if arr[m] < target: # 타겟이 arr[m]보다 크다면
            l = m +1 #한 칸 더 옆에서 실행
        elif arr[m] > target: #작다면
            r = m -1 #한 칸 뒤에서 실행
        else:
            return m #둘 다 아니면 그냥 m출력
    return -1 #while문이 끝나면 -1출력
if __name__ == "__main__": #main.py
    arr = [1,2,3,4,5,6,7,8,9] #배열의 총 길이
    print(binary_search(arr,3)) #타켓이 배열보다 작으므로 3-1 =2
    print(binary_search(arr,7)) #타켓이 배열보다 작으므로 7-1 =6
    print(binary_search(arr,15)) #l > r이므로 -1 출력