[python] 이진탐색 (Binary Search)

✅ 이진탐색이란

• 정렬된 배열에서 탐색의 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘
• 입력 데이터가 많거나 (1,000만 개 이상) 탐색 범위의 크기가 매우 넓을 때 (1,000억 이상) 효과적으로 문제 해결 가능

 

✅ 동작 과정

• 특정 데이터를 찾기 위해 리스트 내 기준점으로 시작 인덱스, 중간 인덱스, 마지막 인덱스를 사용

1. 시작 인덱스와 마지막 인덱스 사이의 중간 값에서 소수점 이하를 버려 중간 인덱스를 정함
2. 중간 인덱스에 해당하는 데이터와 현재 찾으려는 데이터가 같은 지 비교
3. 중간 값이 더 크면 중간 인덱스 이후의 값은 확인하지 않고, 마지막 인덱스를 중간 인덱스로부터 한 칸 앞으로 옮김  (반대로 중간 인덱스 값이 더 작다면 시작 인덱스를 중간 인덱스로부터 한 칸 뒤로 옮김)
4. 중간 인덱스의 값과 찾으려는 값이 같아질 때까지 2와 3의 과정을 반복함

▶ 예시

 

✅ 구현 1 (반복문)

def binary_search(arr,target,start,end):
    while start<=end:
        mid=(start+end)//2

        if arr[mid]==target:
            return mid
        elif arr[mid]>target:
            end=mid-1
        else: #arr[mid]<target
            start=mid+1
    return None

arr =[0,2,4,6,8,10,12,14,16,18]
n=len(arr)
target=4
result=binary_search(arr,target,0,n-1)
print("{}번째에서 타겟 확인".format(result+1))

 

✅ 구현 2 (재귀)

def binary_search(arr,target,start,end):
    if start>end:
        return None

    mid=(start+end)//2

    if arr[mid]==target:
        return mid
    elif arr[mid]>target:
        return binary_search(arr,target,start,mid-1)
    else: #arr[mid]<target
        return binary_search(arr,target,mid+1,end)

arr =[0,2,4,6,8,10,12,14,16,18]
n=len(arr)
target=4
result=binary_search(arr,target,0,n-1)
print("{}번째에서 타겟 확인".format(result+1))

 

✅ 결과

 

✅ 시간 복잡도 (Big-O)

• 탐색 횟수별로 확인하는 데이터의 개수가 절반씩 줄어들기 때문에 O(log N)
• 데이터의 개수가 절반씩 줄어드는 특징은 퀵 정렬과 동일

▶ O(log N) 인 이유