파이썬 알고리즘 - 이진탐색 알고리즘(binary search algorithm for python)

안녕하세요 jay입니다.

오늘은 파이썬으로 이분탐색(binary search)에 대해 알아보겠습니다.

1. 이진탐색 알고리즘(Binary Search Algorithm)

이진탐색 알고리즘이란 정렬된 데이터를 기준으로,

*중간 위치를 찾아 찾는 값과 중간 위치 값을 비교합니다.

먼저 시작 인덱스와 맨 끝인덱스, 중간 인덱스를 선정합니다.

만약 찾는 값이 중간 위치 값보다 크면, 현재 중간 인덱스의 다음 인덱스를 시작 인덱스로 옮깁니다.

만약 찾는 값이 중간 위치 값보다 작으면, 중간 인덱스의 이전 인덱스를 끝 인덱스로 옮깁니다.

그리고 *로 돌아가 계속 반복해서 원하는 값을 탐색하는 알고리즘입니다.


2. 시간 복잡도

결론부터 말씀드리면 이진탐색 알고리즘의 시간복잡도는 O(logN)입니다.
간단하게 증명을 해보면
처음 입력한 데이터숫자를 N이라고 가정합니다.
첫 시행때 1/2 *N
두번째 시행때 1/2 * 1/2 * N
세번째 시행때 1/2 * 1/2 * N

즉 시행횟수를 K라고 둔다면

(1/2)^K * N = 1(1에 수렴을 의미)이라고 볼 수 있습니다.
여기에 2^K를 곱하면
N = 2^K이고 여기에 양변에  로그를 취하면
K =  입니다.
즉 자료갯수에 따른 시행횟수, 시간 복잡도는 Big O표기법으로 O(logN)이라는 것을 알 수 있습니다.
(상수부분은 무시)

3. 소스코드

# binary_search Algorithm
def binary_search(a,x):
    start = 0
    end = len(a)-1
    
    while start <= end:
        mid = (start+end)//2
        
        if x == a[mid]:
            return mid
        
        elif x > a[mid]: 
            start = mid +1
            
        else:
            end = mid-1
                        
    return -1

a = [1,4,9,16,20,24,30,49,84]
inputNum = int(input("input number you wanna find: "))

c =binary_search(a, inputNum)
print("It is index of number you wanna find: ",c)

4. 나의 뻘짓 방식

위처럼 인덱스를 활용하여 위치값만 반환하는 코드를 만들면 되는데,

나같은 경우 찾는 값보다 작거나 크면, 기존 리스트를 일일이 슬라이싱해서

원래 인덱스를 찾아내는 로직을 또 다시 짜야했다.