[알고리즘 일기] 4. 이진 탐색 구현 알고리즘(재귀)

 

 

문제 04. (2021-05-04)

이진 탐색 구현 알고리즘(재귀)

이진 탐색을 재귀로 구현해보세요.

 

 

주의사항

* 반드시 재귀(recursion)의 개념을 사용해야 합니다.

 

 

❧ 테스트 셋

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index's default value
    if end_index == None:
        end_index = len(some_list) - 1

    # 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

 

---

❧ 정답

Try 1

def binary_search(element, some_list, start_index=0, end_index=None):
    if end_index == None:
        end_index = len(some_list) - 1
    if (element == some_list[start_index]):
        return start_index
    elif (start_index == end_index):
        return None
    else:
        return binary_search(element, some_list, start_index + 1, end_index)

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]))

 

1️⃣ 단순 순차 탐색 알고리즘으로 구현

: 결과는 동일하게 나올 수 있으나, 문제에서 제시한 이진 탐색 알고리즘이 아님

시간 복잡도 : O(n)

 

 

 

Try 2

def binary_search(element, some_list, start_index=0, end_index=None):
    if end_index == None:
        end_index = len(some_list) - 1

    # 끝까지 탐색 완료
    if start_index > end_index:
        return None
      
    # 중간 인덱스 탐색
    mid = (start_index + end_index) // 2
  
    if some_list[mid] == element:
        return mid

    # [요소 값] < [중간 값], 왼쪽 탐색
    if element < some_list[mid]:
        return binary_search(element, some_list, start_index, mid - 1)

    # [요소 값] > [중간 값], 오른쪽 탐색
    else:
        return binary_search(element, some_list, mid + 1, end_index)        

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]))

 

1️⃣ 입력 리스트의 값이 순차 정렬되어 있는 경우에만 가능

2️⃣ 중간 값 도출을 통해 탐색 진행에 따라 탐색 범위가 반씩 줄어듦

시간 복잡도 : log(n)