재귀함수 연습문제: 이진탐색 재귀로 구현

내 답안

이진탐색 재귀 구현은 베이스 케이스가 두 가지로 앞의 문제와 차별점이 있음. 두가지 케이스는 element가 리스트에 존재할 때와 안할 때로 나뉨.

base case:

1. element가 리스트에 존재하고, mid_index와 element값이 같을 때
2. element가 리스트에 존재하지않음. -> 어떻게 판단할 것인가가 문제
   -> 리스트에 요소가 하나만 남았고(start_index == end_index or end - start == 0), 이 요소가 element와 일치 하지 않는다면 리스트에 없다고 판단.

recursive case:

1. mid_index가 element보다 크면 mid_index 이후인 오른쪽은 앞으로 참고 안해도 됨. 따라서 end_index에 mid_index를 넣어줘 리스트에서 참고할 범위를 반으로 줄임.

2. mid_index가 element보다 작으면 mid_index 이전인 왼쪽은 앞으로 참고안해도 됨. 따라서 start_index에 mid_index를 넣어줘 리스트에서 참고할 범위를 반으로 줄임

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    
    #Base case
    if end_index == None:
        end_index = len(some_list) - 1
    mid_index = (start_index + end_index ) //2
    
    if some_list[mid_index] == element:
        return mid_index
    elif end_index - start_index == 0 and some_list[mid_index] != element:
        return None
    
    #recursive case
    if some_list[mid_index] > element:
        return binary_search(element, some_list, end_index=mid_index)
    elif some_list[mid_index] < element:
        return binary_search(element, some_list, start_index=mid_index+1)    
        
        
        
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

해답

처음에는 end_index가 None으로 시작하고, 이후에는 mid_index를 이용해 범위를 줄여줌. 따라서 코드의 흐름이 논리적임.

1. 모든 처음의 경우에는 end_index는 None으로 시작함

2. 순환이후 element가 리스트에 없는 경우 배제:
   해답은 베이스케이스의 element가 리스트에 존재하지 않을 때를 start_index가 end_index보다 커질 때라고 표현함.

3. 중간 인덱스 찾기

4. 중간 인덱스가 element와 같은 값인지 비교

5. 중간 값 대소 비교
   positional argument를 사용했구나!!

return binary_search(element, some_list, start_index, mid - 1)

마지막의 end_index부분에 mid-1을 위치시켜서 결국 end_index값이 mid-1값으로 argument를 받게됨

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1

    # start_index가 end_index보다 크면 some_list안에 element는 없다
    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]))