9-2 . Recursion으로 Binary Search의 여러가지 Case 코딩해보기

 

 

1) Binary Search 에서 List 는 이미 Sort 되어 있지만 찾고자 하는 Value가 Duplicate 되어 있을 때

 

- Middle을 찾았을 때 Term만 좀 While문으로 만져주면 될 거 같다.

- Recursion으로도 구현할 수 있을 거 같긴 한데.. 일단 While문으로!

---

 

Recursion을 이용해서도 해당 코드를 구현해보았다.

 

다소 조잡한 감이 있어도 코드는 잘 돌아가서 다행이다..ㅎㅎ

 

특이점으론, Recursion 함수를 잘 만들어 놓고 해당 함수를 binary_search에 넣었을 때 자꾸 무한루프를 돌면서 코드가 버벅거렸다.

 

이유를 찾아보니..

 

recursion함수를 binary_search에서 사용할 때에도 return을 이용해서 사용해야 하는데 그냥 함수만 Call해서 그랬던 것이었다.

 

return을 하지 않으면 recursion이 알아서 돌고, 다시 원래 binary_search 함수의 while문이 돌게 되어 무한히 recursion과 while문 내 함수가 반복되는 현상이 발생한다.

 

기초적인 부분인듯한데, 내가 코드를 짜는 경험이 많이 없어서 실수를 했다.

 

혼자 연습할 때 이런 실수를 한 것이 다행이라고 생각된다.

 

에횽~

​# Duplicate가 많을 때 가장 왼쪽 값을 Return 하기 # Recursion 사용
​
lst1 = [-100,-50,-19,-7,0,3,3,3,7,123] # Expected ans : 5
lst2 = [-100,-50,3,3,3,3,3,3,7,123] # Expected ans : 2
lst3 = [-100,-50,-19,-7,3,3,3,3,3,123] # Expected ans : 4
lst4 = [3,3,3,4,5,6,7,8,9,100,1234] # Expected ans : 0
lst5 = [3,3,3,3,3,3,3,3,3,3,3,3,3,4,5,6,7,8,9,100,1234] # Expected ans : 0
def left_recursion(lst,value,x):
    if lst[x] != value:
        #'base'
        return x+1
    else :
        #'general'
        return left_recursion(lst,value,x-1)
    
def binary_search(lst:list,value:int) -> int:
    first = 0
    last = len(lst)-1
    while first <= last :
        middle = (first+last) // 2
        if lst[middle] == value:
            return left_recursion(lst,value,middle)   # recursion 쓸 때에도 Return 꼭 붙쳐주기!! 아니면 코드는 상위 while에서 무한루프
        
        elif lst[middle] > value :
            last = middle - 1
        else :
            first = middle + 1
    return -1
​
print(binary_search(lst1,3),binary_search(lst2,3),binary_search(lst3,3),binary_search(lst4,3),binary_search(lst5,3))
5 2 4 0 0

 

# Duplicate가 많을 때 가장 오른쪽 값을 Return 하기 # Recursion 사용
​
lst1 = [-100,-50,-19,-7,0,3,3,3,7,123] # Expected ans : 7
lst2 = [-100,-50,3,3,3,3,3,3,3,7,123] # Expected ans : 8
lst3 = [-100,-50,-19,-7,1,2,3,3,3,3] # Expected ans : 9
lst4 = [-100,-50,-19,-7,1,2,3,3,3,7] # Expected ans : 8
​
def right_recursive(lst,value,x):
    if x == len(lst):
        return x-1
    elif lst[x] != value :
        return x-1
    else :
        return right_recursive(lst,value,x+1)
​
def binary_search(lst:list,value:int) -> int:
    first = 0
    last = len(lst)-1
    while first <= last :
        middle = (first+last) // 2
        if lst[middle] == value:
            return right_recursive(lst,value,middle)
        
        elif lst[middle] > value :
            last = middle - 1
        else :
            first = middle + 1
    return -1
print(binary_search(lst1,3),binary_search(lst2,3),binary_search(lst3,3),binary_search(lst4,3))
7 8 9 8