Binary Search

이진 탐색 알고리즘

• 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  • 이진 탐색은 시작점, 끝점, 중간점 이용하여 탐색 범위 설정

이진탐색 소스코드

def binary_search(array, target, start, end) :
    if start > end :
        return None
    mid = (start+end)//2

    if array[mid] == target :
        return mid
    elif array[mid] > target :
        return binary_search(array, target, start, mid-1)
    else :
        return binary_search(array, target, mid+1, end)  

n,target = list(map(int, input().split()))
array = list(map(int,input().split()))

result = binary_search(array, target, 0, n-1)
if result == None :
    print("원소 존재 x")
else:
    print(result+1)

---

이진탐색 반복문

def binary_search(array, target, start, end) :
    while start <= end :
        mid = (start+end) // 2

        if array[mid] == target :
            return mid
        elif array[mid] > target :
            end = mid - 1
        else :
            start = mid + 1

    return None

n,target = list(map(int, input().split()))
array = list(map(int,input().split()))

result = binary_search(array, target, 0, n-1)
if result == None :
    print("원소 존재 x")
else:
    print(result+1)

• 단계마다 탐색 범위를 2로 나누는 것과 동일 → 연산 횟수 $logN$에 비례
• 이진 탐색은 탐색 범위를 절반씩 줄이며 시간복잡도 $O(logN)$을 보장

---

파이썬 이진 탐색 라이브러리

• bisect_left(a,x) : 정렬된 순서를 유지하며 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a,x) : 정렬된 순서를 유지하며 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환

from bisect import bisect_left, bisect_right

a = [1,2,4,4,8]
x = 4

print(bisect_left(a,x)) # 2
print(bisect_right(a,x)) # 4

활용 : 값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value) :
    right_index = bisect_right(a, right_value)
    left_index  = bisect_left(a, left_value)
    return right_index-left_index

a = [ 1,2,3,3,3,3,4,4,8,9]
print(count_by_range(a,4,4)) # 2
print(count_by_range(a,-1,3)) # 6

---

파라메트릭 서치(Parametric Search)

최적화 문제를 결정 문제(”예” 혹은 “아니오”)로 바꾸어 해결하는 기법

• 예) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

→ 이진탐색을 이용해 해결