이진 탐색 구현

Q

‘이진 탐색(Binary Search)’ 알고리즘을 사용해서 어떤 원소가 리스트 안에 포함되어 있는지 확인하려고 합니다. 이진 탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 합니다. 정렬된 리스트가 아니면 이 알고리즘은 적용이 불가능합니다.

 

A

def binary_search(element, some_list):
    start_index = 0 
    end_index = len(some_list) - 1  # 인덱스는 0부터 시작하기 때문에 -1
    
    #반복문
    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2  # //는 버림 나눗셈
        if some_list[midpoint] == element:  # 동일한 값이 나올 때까지 반복
            return midpoint
        elif element < some_list[midpoint]:  # 반복문 조건의 조정
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1
    return None    


print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

 

</> 실행 결과

0
None
2
1
4