[코드잇][알고리즘의 정석]토픽 1: 하나의 문제, 여러 가지 알고리즘-04. 이진 탐색 구현해보기

[코드잇][알고리즘의 정석]토픽 1: 하나의 문제, 여러 가지 알고리즘-04. 이진 탐색 구현해보기

 

링크: https://www.codeit.kr/learn/courses/algorithms/1028

코딩이 처음이라면, 코드잇

---

문제

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

왜 이 알고리즘의 이름이 ‘이진 탐색’일까요? 1회 비교를 거칠 때마다 탐색 범위가 (대략) 절반으로 줄어들기 때문입니다.

예시

예를 들어 [1, 2, 3, 5, 8, 13, 21, 34, 55]에서 3을 찾는 경우, 알고리즘의 진행 방식은 다음과 같습니다:

시도 1

리스트의 첫 번째 인덱스와 마지막 인덱스의 값을 합하여 2로 나눈 후, 중간 인덱스로 지정합니다. 그리고 그 인덱스에 해당하는 값이 3인지 확인해봅니다.

이 경우 리스트의 첫 번째 인덱스는 0이고 마지막 인덱스는 8이기 때문에, 중간 인덱스는 4이고 해당 원소는 8입니다. 찾고자 하는 원소(3)는 중간 원소(8)에 비해 작습니다. 리스트는 정렬되어 있으니, 이제 인덱스 4~8은 탐색 범위에서 제외시킬 수 있습니다. 탐색 범위가 절반으로 줄어든 것이죠.

시도 2

탐색 범위는 이제 인덱스 0~3입니다. 탐색 범위의 첫 번째 인덱스는 0이고 마지막 인덱스는 3이기 때문에, 중간 인덱스는 (0 + 3) // 2인 1입니다. 인덱스 1에 해당하는 원소는 2이죠.

찾고자 하는 원소(3)는 중간 원소(2)에 비해 큽니다. 리스트는 정렬되어 있으니, 이제 인덱스 0~1은 탐색 범위에서 제외시키면 됩니다. 탐색 범위가 다시 절반으로 줄어든 것이죠.

시도 3

탐색 범위는 이제 인덱스 2~3입니다. 탐색 범위의 리스트의 첫 번째 인덱스는 2이고 마지막 인덱스는 3이므로, 중간 인덱스는 (2 + 3) // 2인 2입니다. 인덱스 2에 해당하는 원소의 값은 3이죠.

찾고자 하는 원소(3)는 중간에 해당하는 원소(3)와 일치합니다. 값을 찾았으니, 인덱스 2를 리턴해주며, 알고리즘을 종료합니다.

def binary_search(element, some_list):
    # 코드를 작성하세요.

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):
    # 코드를 작성하세요.
    first_index = 0
    last_index = len(some_list) - 1
    
    while first_index <= last_index :
        i = (first_index + last_index)//2

        if element == some_list[i]:#같을때
            return i
        elif element < some_list[i]:#요소가 더 작을때
            last_index = i - 1
        else:#요소가 더 클때
            first_index = i + 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]))