Binary Search

이진탐색 알고리즘은 분할정복 방법론을 활용한 탐색알고리즘입니다.

 

이진탐색 알고리즘의 순서를 살펴보면

1. Data를 오름차순으로 정렬한다.

2. Data의 중간위치의 값과 내가 찾을 값을 비교한다

if       내가 찾을 값 = 중간위치값 -> 탐색끝

else if 내가 찾을 값 < 중간위치값 -> 1~중간값 이전까지의 데이터에서 다시 이진탐색

else if 내가 찾을 값 > 중간위치값 -> 중간값+1~마지막까지의 데이터에서 다시 이진탐색

 

보면 알수있지만, 한번 탐색을 하고, 그 이후에 데이터를 분할하여 다시한번 알고리즘을 적용한다.

 

때문이 이러한 알고리즘은 분할정복 알고리즘이라고 부릅니다.

 

이진탐색 알고리즘의 성능은

T(n) = T(n/2) + O(1), T(1) = 1

을 보입니다. 이걸 점화식을 풀어주면

T(n) = logn의 성능을 보여주는것을 알 수 있게됩니다.

 

Python으로 구현한 이진탐색 알고리즘은 아래와 같습니다.

import random
#예시를 위해서 0~99999까지의 값이 있는 List를 생성합니다.
Data = [i for i in range(100000)]
#0~99999 사이의 랜덤값을 생성합니다.
find_key = random.randrange(0, 99999)
#이진 탐색 알고리즘을 정의합니다.
def binary_search(DT_list, key, offset=0):
    #List의 중간점 의 데이터와 찾고자 하는 값과 비교
    mid_loc = int(round(len(DT_list)/2))
    #List의 중간값과 찾고자 하는 값이 있으면 종료
    if DT_list[mid_loc]==key:
        return print("find_key is exist in %d" %(mid_loc+offset))
    #List의 좌측 부분배열에서 이진탐색
    elif DT_list[mid_loc]>key:
        binary_search(DT_list[0:mid_loc], key, offset = offset)
    #List의 우측 부분배열에서 이진탐색
    elif DT_list[mid_loc]<key:
        binary_search(DT_list[mid_loc+1:], key, offset = offset+mid_loc+1)
binary_search(Data, find_key)    

100000개의 값이 존재하는 정렬된 List를 생성하고

여기서 난수를 생성하여 해당 난수의 위치를 확인할 수 있습니다.