[Algorithm] 이분탐색 (Binary Search) - 변형

1. Lower bound

- 배열에 해당 값이 두개 이상 존재하는 경우 가장 앞선 인덱스를 반환하도록 한다. 

def binary_search_lo(given_data,target):
    start = 0
    end = len(given_data)-1

    while start<=end:
        mid = (start + end)//2
        if given_data[mid] < target: 
            start = mid + 1
        else:
            end = mid - 1
            
    return start

data = [3,4,5,1,1,1,1,3,3,4]
data.sort()
print(data) #정렬된 data(리스트)를 출력
res = binary_search_lo(data, 3) #가장 앞서 위치한 3의 인덱스

print(res)

output 

[1, 1, 1, 1, 3, 3, 3, 4, 4, 5]

4

 

과정

start, end를 계산하여 given_data의 범위를 제한한다.

start가 end와 보다 작거나 같을동안 진행한다.

given_data[mid]가 target보다 작다면 start = mid + 1, 아니라면 end = mid-1을 수행한다.

최종적인 given_data[start: end+1]에는 target값이 없다.

start, end, mid가 같아진다

given_data[mid]는 target보다 무조건 작기 때문에 start = mid+1을 수행 한 후  start 인덱스 반환 후 반복문이 종료된다.

이때의 given_data[start]는 target값이 지작하는 위치의 인덱스이다. 

 

2. Upper bound

- 배열에 해당 값이 두개 이상 존재하는 경우 가장 나중의 인덱스를 반환하도록 한다. 

def binary_search_up(given_data,target):
    start = 0
    end = len(given_data)-1

    while start<=end:
        mid = (start + end)//2
        if given_data[mid] <= target:
            start = mid + 1
        else:
            end = mid-1
            
    return start-1

data = [3,4,5,1,1,1,1,3,3,4]
data.sort()
print(data)
res = binary_search_up(data, 3)

print(res)

output

[1, 1, 1, 1, 3, 3, 3, 4, 4, 5]

6

 

과정

start, end를 계산하여 given_data의 범위를 제한한다.

start가 end와 보다 작거나 같을동안 진행한다.

given_data[mid]가 target보다 작거나 같다면 start = mid + 1, 아니라면 end = mid-1을 수행한다.

최종적인 given_data[start: end+1]에는 target값이 없다.

start, end, mid가 같아진다

given_data[mid]는 target보다 무조건 크기 때문에 start = mid+1을 수행 한 후  start-1 인덱스 반환 후 반복문이 종료된다.

이때의 given_data[start]는 target값이 끝나는 위치의 인덱스이다.