8. 이진 검색

---

 

 

1. 이진 검색 (Binary Search)

이진 검색 알고리즘이란, 원소가 오름차순이나 내림차순으로 정렬된 배열에서 효율적으로 검색할 수 있는 알고리즘이다.

이진 검색 트리를 기반으로 동작하며, 주목한 원소보다 값이 크면 우측으로, 값이 작으면 좌측으로 움직이면서 검색을 진행한다.

주목한 원소가 이동할 때마다 검색 범위가 1/2로 줄어든다.

정렬된 배열에 대해서 선형 검색보다 매우 빠르게 검색이 가능하다.

이진 검색의 종료 조건은 다음과 같다.

• 중앙 원소가 키 값과 일치하는 경우, 검색 성공
• 검색 범위가 더 이상 없는 경우, 검색 실패

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any) -> int :
    pl = 0
    pr = len(a) - 1
    
    while True:
        pc = (pl + pr) // 2
        
        if (a[pc] == key) :
            return pc
        elif (a[pc] < key) :
            pl = pc + 1
        else :
            pr = pc - 1
        
        if (pl > pr) :
            break
    return -1
    
    
if (__name__ == '__main__') :
    num = int(input("원소 수: "))
    x = [None] * num
    
    print("배열 데이터를 오름차순으로 입력하세요.")
    
    x[0] = int(input("x[0]: "))
    
    for i in range(1, num) :
        while (True) :
            x[i] = int(input(f"x[{i}]: "))
            
            if (x[i] >= x[i-1]) :
                break
            
        ky = int(input("검색할 값: "))
        idx = bin_search(x, ky)
        
        if (idx == -1) :
            print("원소 없음")
        else :
            print(f"검색값: x[{idx}]")

pl: 검색 범위의 맨 앞 (== 0)

pr: 검색 범위의 맨 끝 (== n-1)

pc: 중앙 원소 인덱스 (== (pl+pr)//2)

a[pc] < key: pc+1을 새로운 pl로 지정해 검색 범위를 뒤쪽 절반으로 줄인다.

a[pc] > key: pc-1을 새로운 pr로 지정해 검색 범위를 앞쪽 절반으로 줄인다.

pl > pr: 검색할 범위가 더 이상 없음 (검색 실패)

 

---

 

2. 복잡도 (Complexity)

알고리즘의 성능을 객관적으로 평가하는 기준이 되는 값.

시간 복잡도(Time Complexity)란, 코드를 실행하는데 필요한 시간을 평가하한다.

알고리즘 수행에 기본이 되는 명령어가 입력 데이터 크기(n)에 대해 수행되는 횟수로 표기한다.

직접 수행 시간을 측정하는 대신, 입력 데이터 개수 n에 대한 함수로 결정한다.

공간 복잡도(Space Complexity)란, 메모리와 파일 공간이 얼마나 필요한 지를 평가한다.

 

2.1) 점근적 상한: O(f(n)) Big-O

최고차항의 차수가 f(n)과 일치하거나, 작은 함수의 집합.

점근적 증가율이 f(n)을 넘지 않는 모든 함수의 집합.

5n^2 + 4n의 증가율이 n^2의 증가율과 '점근적인 의미에서' 동일하기 때문에, 5n^2 + 4n == O(n^2)이 된다.

7n의 증가율은 n^2의 증가율보다 작기 때문에, 7n == O(n)이 된다.

g(n) == O(f(n))은 어떤 함수 g(n)이 함수 f(n)보다 점근적인 관점에서 빠르게 증가하지 않는다는 것을 의미하며, 이는 어떤 함수의 '점근적 상한'을 의미한다.

O(f(n)) + O(g(n)) == O(max(f(n), g(n)))

 

2.2) 선형 검색의 시간 복잡도

def seq_search(a: Sequence, key: Any) -> int :
    i = 0
    
    while (i < n) :
        if (a[i] == key) :
            return i
        
        i += 1
        
    return -1

종료 조건 판단의 평균 실행 횟수: (n+1) / 2 == O(n)

O(1) + O(n) + O(n) + O(1) + O(n) + O(1) == O(max(1, n, n, 1, n, 1)) == O(n)

 

2.3) 이진 검색의 시간 복잡도

def bin_search(a: Sequence, key: Any) -> int :
    pl = 0
    pr = len(a) - 1
    
    while (True) :
        pc = (pl + pr) // 2
        
        if (a[pc] == key) :
            return pc
        elif (a[pc] < key) :
            pl = (pc + 1)
        else :
            pr = (pc - 1)
        
        if (pl > pr) :
            break
        
return -1

종료 조건 판단의 평균 실행 횟수: log2 n == O(log n)

O(1) + O(1) + O(log n) + O(log n1) + ~ + O(1) == O(log n)

 

2.4) 복잡도와 증가율

크기가 작은 문제는 알고리즘의 효율성이 중요하지 않으며, 비효율적인 알고리즘도 무방하다.

하지만 크기가 충분히 큰 문제는 알고리즘의 효율성이 중요하며, 비효율적인 알고리즘은 치명적이다.

 

---

 

---

수고하셨습니다!

---