이진 탐색 알고리즘

이진 탐색을 알기 전에 먼저 순차탐색의 개념을 이해해야합니다. 순차 탐색은 순서대로 특정데이터를 찾기 위해 앞에서 부터 확인하는 방법입니다.

 

순차 탐색 코드 예제

data = ["apple","graph","tomato","pear"]
find = "tomato"


def Seq(da,fi):
    for i in range(len(da)):
        if da[i] == fi:
            return i+1

print(Seq(data,find))

해당하는 과일의 인덱스를 순서대로 비교해 찾은 후 반환하는 순차탐색의 예제입니다. 이 처럼 순차탐색은 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 특징이 있습니다.

 

이진탐색

이진 탐색은 시작점, 끝점, 그리고 중간점을 기준으로 데이터를 반으로 쪼개면서 탐색하는 알고리즘입니다. 이진 탐색을 적용하기 위해서는 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다. 

아래의 리스트를 가지고 23을 찾는 이진탐색을 설명하겠습니다. 

0

3

8

11

23

34

(시작점을 기준으로 정답과 값을 비교)

1. 시작점 : 0 끝점 :34 중간점 :8 , 중간점 아래에 값은 확인할 필요가 없으므로 중간점을 시작점으로 옮기고 새로운 중간점을 선정합니다.

2.시작점 : 8,끝점 :34,중간점 : 23, 중간점이 값이 찾으려는 값과 같으므로 탐색을 종료합니다.

 

예제 코드

def binary_search(a,target,start,end):
    if start > end : 
        return None
    mid = (start+end)//2
    if a[mid] == target:
        return mid

    elif a[mid] > target:
        return binary_search(a,target,start,mid-1)
    else:
        return binary_search(a,target,mid+1,end)


b = [0,3,8,11,23,34]
find = 23
result = binary_search(b,find,0,len(b))

print(result)

시작점과 끝점이 교차되는 경우 : 값이 존재하지 않음

중간 값이 찾는 값과 같은 경우 : 정답 위치 반환

중간값이 찾는 값보다 클 경우 : 끝점을 중간값으로 변경

중간값이 찾는 값보다 작을 경우 : 시작점을 중간값으로 변경으로 코드를 이해하시면 됩니다.

 

시간 복잡도

퀵정렬 처럼 탐색을 진행하면 진행할 수록 탐색할 리스트의 개수가 반으로 줄게 되어있습니다. 따라서 빅오 표기법으로 logN의 속도를 내며 정렬된 수많은 양의 리스트에서 검색해야할 경우 사용하면 좋습니다.

 

이진탐색은 트리에서도 사용이 가능한데 아래에 링크에서 사용법을 알 수 있습니다.

 

위키 설명

이진 탐색 위키 설명보러가기

이진 탐색 트리 - 위키백과, 우리 모두의 백과사전