[파이썬 | 알고리즘] 이진 탐색(Binary Search)

지난번에는 병합 정렬(Merge Sort)에 대해 알아보았습니다.

이번에는 이진 탐색Binary Search)에 대해 알아보겠습니다.

이진 탐색(Binaray Search)

이진 탐색은 데이터리스트가 기본적으로 정렬이 되어 있을 때 탐색 할 데이터리스트를

재귀용법을 이용해 둘로 나누어 데이터가 있을만한 곳을 탐색해나가는 탐색 알고리즘이다.

 

이진 탐색(Binaray Search)의 접근법

탐색 할 데이터리스트의 medium(중간 값)을 설정 후 medium보다 작으면 

medium 이전값까지 재 탐색 medium보다 크면 medium 이후값 재 탐색

 

패턴 분석

정렬 된 데이터 리스트는 10, 11, 18, 36, 42, 68, 71, 95이다. (Medium = int(len(data) //2) )

탐색 할 데이터 : 11 // search_data=11

●Medium(중간 값) 데이터보다보다 작으면 medium이전 값 재 탐색, 크면 medium이후 값 재 탐색

				medium
10	11	18	36	42	68	71	95

medium = 42

medium > search_data

medium 이전 값 재 탐색

		medium
10	11	18	36

medium = 18

medium > search_data

medium 이전 값 재 탐색

	medium
10	11

medium == search_data

탐색완료

 

이진 탐색 구현 (파이썬 | Binaray Search)

def binary_search(data, search):
    #방어코드 기재
    print (data) 
    if len(data) == 1 and search == data[0]: #데이터가 1개이면서 탐색 할 데이터이면 True 
        return True
    if len(data) == 1 and search != data[0]: #데이터가 1개이고 탐색 할 데이터가 없으면 False
        return False
    if len(data) == 0: #데이터가 0개이면 탐색 할 데이터가 없으니 False
        return False
    
    medium = len(data) // 2     #medium(중간 값) 지정
    if search == data[medium]:  #탐색 할 데이터가 medium값이면 True
        return True
    else:                                
        if search > data[medium]: #탐색 할 데이터가 meidum보다 작으면
            return binary_search(data[medium+1:], search) #medium 이전 값 재 탐색
        else:                     #탐색 할 데이터가 medium보다 크면
            return binary_search(data[:medium], search)  #medium 이후 값 재 탐색

 

코드 테스트(파이썬 |  Binaray Search)

이진 탐색 코드 테스트

테스트 결과

이진 탐색 구현 코드가 정상적으로 구현됨

 

이상으로 [파이썬 | 알고리즘] 이진 탐색에 대해 알아보았습니다,