[ Python_알고리즘 ] 이진 탐색 재귀 함수

[ 이진 탐색 ]

 

이진 탐색 : 리스트를 1회 비교를 거칠 때마다 탐색 범위가 절반으로 줄어든다.

 

# 이진 탐색 반복문

def binary_search( element, my_list ) :
	start = 0
    end = len(my_list)-1
    while start < end : 
    	middle = ( start + end ) // 2
        if element == my_list[middle] :
        	return middle
        elif element < my_list[middle] :
        	end = middle - 1
        else : # element > my_list[middle]
        	start = middle + 1
            
	return None
    
print( binary_search( 6, [2,3,5,6,8,9,10,11] )

 

 

def binary_search(element, my_list, start_index=0, end_index=None):

    if end_index == None:
        end_index = len(my_list) - 1

    # start 인덱스와 end 인덱스가 같아질 경우도 있기 때문에 미리 설정해야함
    if start_index > end_index:
        return None

    middle = (start_index + end_index) // 2
    if element == my_list[middle]:
        return middle
    elif element < my_list[middle]:
        return binary_search(element, my_list, start_index, middle - 1)
    elif element > my_list[middle]:
        return binary_search(element, my_list, middle + 1, end_index)
    else:
        return None


print(binary_search(8, [3,6,7,8,9,11,15,20,23,24,31]))