재귀(Recursion)를 활용해 이진 검색을 구현하려면, 'high' 인덱스가 'low' 인덱스보다 크거나 같은지를 먼저 확인하는 메서드를 정의하면 됩니다. 이후 'mid' 인덱스에 위치한 값을 기준으로 검색 범위를 절반씩 좁혀가며 자기 자신(함수)을 다시 호출하는 방식으로 원하는 요소를 찾습니다.
참고로 파이썬의 리스트(List)는 정수, 실수, 문자열 등 서로 다른 데이터 타입의 값을 함께 저장할 수 있어 유연하게 활용할 수 있습니다.
이진 검색은 반드시 정렬된 리스트에서만 올바르게 동작한다는 점을 기억해야 합니다. 아래는 재귀로 구현한 전체 예제 코드입니다.
예제 코드
def binary_search(my_list, low, high, elem):
if high >= low:
mid = (high + low) // 2
if my_list[mid] == elem:
return mid
elif my_list[mid] > elem:
return binary_search(my_list, low, mid - 1, elem)
else:
return binary_search(my_list, mid + 1, high, elem)
else:
return -1
my_list = [ 1, 9, 11, 21, 34, 54, 67, 90 ]
elem_to_search = 1
print("The list is")
print(my_list)
my_result = binary_search(my_list,0,len(my_list)-1,elem_to_search)
if my_result != -1:
print("Element found at index ", str(my_result))
else:
print("Element not found!")실행 결과
The list is [1, 9, 11, 21, 34, 54, 67, 90] Element found at index 0
코드 설명
- binary_search라는 이름의 재귀 함수를 정의합니다.
- 이 함수는 리스트, 'low' 변수, 'high' 변수, 그리고 검색할 요소(elem)를 매개변수로 받습니다.
- 'mid' 변수에는 'high'와 'low'의 중간값이 할당됩니다.
- 'mid' 위치의 요소가 찾으려는 값과 일치하면 해당 인덱스를 반환합니다.
- 'mid' 위치의 요소가 검색 대상보다 크면, 왼쪽 절반(mid - 1까지)을 대상으로 함수를 다시 호출합니다.
- 'mid' 위치의 요소가 검색 대상보다 작으면, 오른쪽 절반(mid + 1부터)을 대상으로 함수를 다시 호출합니다.
- 'high'가 'low'보다 작아지면 더 이상 탐색할 범위가 없다는 뜻이므로 -1을 반환합니다.
- 정렬된 리스트를 정의한 뒤, 이를 매개변수로 전달하며 함수를 호출합니다.
- 검색 결과는 변수에 저장되며, 조건문을 통해 콘솔에 출력됩니다.
시간 복잡도
이진 검색은 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에 시간 복잡도는 O(log n)입니다. 반면 처음부터 끝까지 순차적으로 확인하는 선형 검색(O(n))에 비해 대용량 데이터에서 훨씬 빠른 성능을 보여줍니다. 다만, 검색 전에 리스트가 반드시 정렬되어 있어야 한다는 전제 조건이 필요합니다.