이진탐색 파이썬

선형 탐색

[1,2,3,4,5,6,7,8,9,10]

이런 배열에서 5를 선형 탐색으로 찾는다면

[0] = 1 아님

[1] = 2 아니고

[2] = 3 아니고 

[3] = 4 아니네

[4] = 5 맞네

이런 식으로 하나하나 다 찾아야 합니다.

 

근데 만약에 1부터 1000까지 들어있는 배열이 있는데

거기서 448을 찾고 싶다면?

정렬되어있다고 가정하에 448번 검사해야 합니다.

진짜 최악의 경우 없거나 index 999에 있다면

1000번 검사해야 하는 꼴이죠

이진 탐색

이진 탐색은 일단 정렬이 되어있어야지 사용할 수 있습니다.

[1,2,3,4,5,6,7,8,9,10]

이런 배열에서 2를 찾고자 한다면

4에 도착합니다. 근데 지금 찾고자 하는 게 2인데

4가 이보다 크죠 그러니까 자길 포함한 뒤에 애들은 싹 다 버립니다

(배열을 삭제하는 게 아니라 취급을 안 한다는 겁니다)

그럼

[1,2,3,]만 남죠

여기서 또 반절인 2에 도착하게 되는데 찾고자 하는 2를 찾았네요

헐 아까는 하나하나 검사해서 5번 만에 찾았는데 이젠 두 번 만에 찾아버렸네요 대박

 

 

 

 

Python으로 구현

재귀 함수로 구현해보면

def binary_search(arr,n,start,end):
    count = 1
    if start > end: 
        return None
    mid = (start+end)//2 #인덱스의 반절을 미드값으로 잡아야해서 2로나눕니다
    if arr[mid] == n: #만약에 잡은 미드값이 찾고자 하는 값이라면
        return mid #index를 리턴해줍니다
    elif arr[mid] > n: #미드값이 찾고자하는 원소보다 크다면
        return binary_search(arr,n,start,mid - 1) #뒤에 원소들은 버립니다
    else: #미드값이 찾고자하는 값보다 작다면 
        return binary_search(arr,n,mid + 1, end) #시작점을 미드값으로 잡아서 앞에 원소들을 버립니다

 

반복문으로 구현

def repeat_binary(arr,n):
    start = 0
    end = len(arr) - 1
    while start <= end:
        mid = (start+end)//2
        if arr[mid] == n:
            return mid
        elif arr[mid] > n:
            end = mid - 1
        else:
            start = mid + 1

 

이진 탐색 같은 경우는 실제로 사전에서 단어를 찾는다던가 할 때

비슷한 맥락으로 찾아볼 수 있다는 점에서 재밌는 거 같습니다