[알고리즘 일기] 7. 이진 탐색 구현 알고리즘

문제 07. (2021-05-07)

​

이진 탐색 구현 알고리즘

이진 탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 합니다. 정렬된 리스트가 아니면 이 알고리즘은 적용이 불가능합니다.

​

​

주의사항

* 1회 비교를 거칠 때마다 탐색 범위가 (대략) 절반으로 줄어듭니다.

​

​

❧ 테스트 셋

def binary_search(element, some_list):
    # Code

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

 

---

❧ 정답

def binary_search(element, some_list):
    i = len(some_list) // 2
    for i in range(len(some_list)):
        if element == some_list[i]:
            return i
        elif element < some_list[i]:
            i = i // 2
        else:
            i = (len(some_list) - 1 - i) + (i // 2)
    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]))

 

))