사전을 사용하지 않고 이진 검색을 구현해야 하는 경우 목록의 첫 번째 인덱스와 마지막 인덱스를 확인하고 목록의 중간 값을 가져오는 메서드를 정의할 수 있습니다.
그런 다음 확인해야 하는 값과 비교됩니다. 찾으면 값이 반환됩니다. 그렇지 않으면 -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에는 list-1의 길이가 할당됩니다.
- '낮음' 값이 '높음'보다 작거나 같은 경우에만 '중간' 변수에 대한 값을 얻기 위해 비트 단위 바닥 나누기가 수행됩니다.
- 값이 중간 인덱스에 있는 값보다 작으면 먼저 낮은 인덱스에서 중간 인덱스로 요소를 검색합니다.
- 그렇지 않으면 값이 중간보다 크고 높음보다 작으면 중간에서 높은 인덱스로 요소를 검색합니다.
- 이제 목록이 정의되었습니다.
- 위의 목록을 매개변수로 전달하여 메소드를 호출합니다.
- 이 작업의 데이터는 변수에 저장됩니다.
- 이 변수는 콘솔에 표시되는 출력입니다.