리스트에서 특정 요소를 찾아야 할 때, 재귀 호출 없이 이진 검색(binary search)을 구현할 수 있습니다. 이 방식은 리스트의 첫 번째 인덱스와 마지막 인덱스를 기준으로 삼고, 두 인덱스 사이의 중간값을 계산하는 방식으로 동작합니다.
중간 위치의 값과 찾으려는 값을 비교한 뒤, 값이 일치하면 해당 인덱스를 반환하고, 끝까지 찾지 못하면 -1을 반환합니다.
이진 검색은 정렬된 데이터에만 적용할 수 있다는 점을 반드시 기억해야 합니다. 즉, 오름차순 또는 내림차순으로 정렬된 리스트여야만 올바른 결과를 얻을 수 있습니다.
참고로 파이썬의 리스트는 정수, 실수, 문자열 등 서로 다른 자료형의 값을 함께 저장할 수 있는 자료구조입니다.
다음은 이를 구현한 예제입니다.
예제
def binary_search(my_list, elem):
low = 0
high = len(my_list) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if my_list[mid] < elem:
low = mid + 1
elif my_list[mid] > elem:
high = mid - 1
else:
return mid
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, 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에는 0을, 변수 mid에는 0을 초기값으로 할당합니다.
- 변수 high에는 리스트 길이에서 1을 뺀 값을 할당하여 마지막 인덱스를 나타냅니다.
- low 값이 high보다 작거나 같은 동안 while 반복문이 실행되며, 각 반복마다 몫 연산자(//)를 사용해 중간 인덱스(mid)를 계산합니다.
- 중간 인덱스의 값이 찾으려는 값보다 작으면, 검색 범위를 오른쪽 절반(low ~ high)으로 좁혀 다시 탐색합니다.
- 중간 인덱스의 값이 찾으려는 값보다 크면, 검색 범위를 왼쪽 절반으로 좁혀 탐색을 계속합니다.
- 두 조건에 모두 해당하지 않으면 중간 위치의 값이 찾던 값이므로 해당 인덱스를 반환합니다.
- 이후 정렬된 리스트를 하나 정의하고, 이 리스트를 인자로 넘겨 함수를 호출합니다.
- 함수의 반환값은 변수에 저장되며, 이 값을 콘솔에 출력하여 결과를 확인합니다.