9-1 . Binary Search의 여러가지 Case 코딩해보기

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

 

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

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

 

---

https://eglife.tistory.com/27

낄끼빠빠~  Recursion 구현글 첨부

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

---

 

 

# Duplicate가 많을 때 가장 왼쪽 값을 Return 하기
​
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 binary_search(lst:list,value:int) -> int:
    first = 0
    last = len(lst)-1
    while first <= last :
        middle = (first+last) // 2
        if lst[middle] == value:
            while lst[middle] == value:
                middle -= 1
            return middle+1
        
        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 하기
​
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 binary_search(lst:list,value:int) -> int:
    first = 0
    last = len(lst)-1
    while first <= last :
        middle = (first+last) // 2
        if lst[middle] == value:
            while middle < len(lst) and lst[middle] == value:
                middle += 1
            return middle-1
        
        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

 

 

2) Binary Search 에서 찾고자 하는 값이 없을 때, 근사값 위치를 반환하는 방법?

 

- 일단 정확한 값을 못 찾아야 발동되는 알고리즘이니 기존 Binary_search에서 return -1 부분을 수정한다.

- 최종적으로 value를 찾기 위해 narrow하게 계산된 first / last  중에 value보다 크거나 작은 값이 있으므로 이 둘을 비교하여 value와 차이가 적은 값을 반환한다.

 

2
# 원하는 값이 없을 때 근사치 반환하기
​
lst1 = [-100,-50,-19,-7,0,3,4,5,10,123] # expected ans : 7
lst2 = [-100,-50,-19,-7,0,3,4,5,6.1,123] # expected ans : 8
​
​
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 middle
        
        elif lst[middle] > value :
            last = middle - 1
        else :
            first = middle + 1
    if abs(lst[first]-value) < abs(lst[last]-value):
        return first
    else: return last
​
    
print(binary_search(lst1,6),binary_search(lst2,6))
7 8