파이썬 배열 이진 검색

이진 검색

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

 

_이진 검색의 조건은 배열의 데이터가 정렬된 상태이어야 합니다.

 

---

 

배열 a가 아래와 같을 때 우리는 a에서 39라는 값을 찾고 싶습니다.

5

7

15

28

29

31

39

40

44

53

 

 

이진 검색은 검색 범위를 맨 앞, 맨 끝, 중앙의 인덱스를 각각 0, n-1, (n-1) // 2 로 설정합니다.

 

이에 따라 첫번째 검색시 중앙 검색범위 (n-1) // 2 를 이용하여 범위를 줄여나갑니다

 

5

7

15

28

29

31

39

40

44

53

 

_첫번째 검색 범위를 마치고 난 뒤의 배열 a입니다.

39

40

44

53

 

 

 

다시 위 중앙 검색범위 (n-1) // 2 를 이용하여 범위를 줄여나갑니다

 

39

40

44

53

 

_두번째 검색 범위를 마치고 난 뒤의 배열 a입니다.

39

 

 

_예시를 통해서 알 수 있듯이 배열의 원소들이 정렬되어있다는 전제하에서 이진검색은 엄청난 힘을 발휘합니다!

 

 

---

_검색 범위의 맨 앞, 맨 끝, 중앙의 인덱스를 pl, pr, pc 라고 정의해봅시다

 

_이진 검색에서 검색 범위를 좁히는 과정을 정리하면 아래와 같습니다

 

 

 

a[pc] < key(찾고자 하는 값) : 중앙(pc)에서 오른쪽으로 한 칸 이동하여 새로운 왼쪽 끝을 pl로 지정하고, 검색 범위를 뒤쪽 절반으로 좁힙니다.

5

7

15

28

29

31

39(key)

40

44

53

5

7

15

28

29

31

39(key)

40

44

53

39(key)

40

44

53

 

 

a[pc] > key(찾고자 하는 값) : 중앙(pc)에서 왼쪽으로 한 칸 이동하여 새로운 오른쪽 끝을 pl로 지정하고, 검색 범위를 앞쪽 절반으로 좁힙니다.

 

5

7

15(key)

28

29

31

39

40

44

53

5

7

15(key)

28

29

31

39

40

44

53

5

7

15(key)

28

29

 

 

_이진 검색의 종료 조건

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

2. 검색 범위가 더 이상 없는 경우

---

 

이진 검색의 기본 코드는 다음과 같습니다.
_while문 사용

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any) -> int:
    # 시퀀스 a에서 key와 일치하는 원소를 이진 검색

    pl = 0 # 맨 앞 원소 인덱스
    pr = len(a) -1 # 맨 뒤 원소 인덱스 

    while True:
        pc = (pl + pr) // 2 # 중앙 원소 인덱스
        
        if a[pc] == key: # 중앙 원소 인덱스와 키값이 같다면
            return pc
        
        elif a[pc] < key: # 중앙값이 키값보다 작다면
            pc = pc + 1
        
        else: # 중앙값이 키값보다 크다면
            pr = pc -1
        
        if pl > pr:
            break
        
        return -1 # 검색 실패