이진 검색

Preface

 

지난 포스팅에 이어 배열 검색 알고리즘 중 하나인 이진 검색을 공부했다.

 

원래 해시법까지 모두 공부한 후 한번에 글을 작성할 계획이었지만, 이번 장을 공부하는 데 생각보다 긴 시간이 걸려 이렇게 따로 업로드한다.

 

이진 검색 코드를 작성하던 도중 한 가지 의문점이 생겨 이를 해결하고자 새로운 코드를 직접 작성해봤으며, 자세한 내용은 본문에 적어놓았다.

---

 

1. 이진 검색

 

 

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

 

 

- 이진 검색의 종료 조건

1) a[pc]와 key가 일치하는 경우

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}]에 있습니다.')

→ x[0]을 따로 작성한 이유가 이해되지 않아 for 문을 사용하여 range(num)으로 코드를 작성해봤는데, if x[i] >= x[i - 1] 부분에서 int 형과 NoneType 간 크기 비교가 불가능 하다는 오류가 출력되었다. 또한, for 문을 사용하면 x[i]의 값이 이전 값보다 작은 경우 재작성 하는 것이 어려웠다.

 

 

- x의 천장 함수(⌈x⌉) : x보다 크거나 같은 정수 가운데 가장 작은 수를 가리킨다.

→ ex) ⌈3.5⌉ = 4

 

 

- 복잡도 : 알고리즘의 성능을 객관적으로 평가하는 기준

1) 시간 복잡도 : 실행하는 데 필요한 시간을 평가

2) 공간 복잡도 : 메모리(기억 공간)와 파일 공간이 얼마나 필요한지를 평가

 

 

- 복잡도 표기 방법 : O(n)

1) O는 order의 initial이며 'n의 오더', '오더 n'이라고 읽는다.

2) 전체 복잡도는 차원이 가장 높은 복잡도를 선택하는 것이다.

→ 프로그램 내에서 가장 오랜 시간을 소비하는 코드가 복잡도

 

 

- 복잡도 크기 비교 : 1 < log n < n < n log n < n의 (int)승 < n의 k승 < 2의 n승 etc.