검색 알고리즘 - (이진 검색)

이번 글에서 해시법과 이진검색을 같이 포스팅하려 했지만 해시법을 공부하는데 시간이 많이 소요될 것 같아 이진검색 따로 먼저 포스팅 하려한다. 

 

이진검색을 업다운 게임을 예로 들자면 업다운 게임도 원하는 값을 최대한 적은 횟수로 찾아내는 것이다. 그럴 때 가장 좋은 방법은 범위의 중간값을 계속해서 물어보는 것이다.

 

이번 단원은 이러한 원리를 잘 알고 있으면 이해하는데 큰 어려움은 없을 것 같다.

---

이진검색

 

이진검색이란 데이터가 정렬 된 상태에서 선형 알고리즘보다 빠르게 검색할 수 있는 알고리즘이다. 

 

앞서 쉽게 설명을 했었는데 다시한번 정확히 개념을 설명하자면 배열이 정렬된 상태에서 원하는 값과 배열의 중간값을 비교해본다. 이 때 중간값과 같지 않다면 대소비교를 통해 범위를 점점 좁혀나가는 것이다.

 

다음은 실행 코드이다.

def bin_search(a,key):
    pl = 0
    pr = len(a) - 1

    while (1):
        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
            
            
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}]')

위 코드는 책에서 나온 코드이다. bin_search함수가 이진검색 알고리즘인데 pl은 배열의 첫번째 pr은 배열의 마지막 pc는 배열의 중간 값이다.  

 

나도 이론을 다 알고있다고 생각해서 아래 코드를 혼자 짜보았는데 내 생각과는 달리 이상한 값이 나올 때도 여러번 있었다.

 

어디서 이런 오류값이 나오는지 찾지 못해 우선 현재까지의 코드를 올려놓고 추후 수정해야겠다.

# 이진검색 알고리즘

a_list = []
def binary_search(a: list,key):
    pl = 0                  # 배열의 시작지점
    pr = len(a) - 1         # 배열의 끝지점
    pc = (len(a) - 1) // 2  # 배열의 중간지점

    a.sort()				# 리스트를 정렬

    while key != pc:		# pc값이 key값과 같아질 때까지 실행

        if key > pc:		# pc 값이 key값보다 작을 때
            pl = pc
            pc_index = int((pr - pl) // 2)
            pc = a[pc_index]

        elif key < pc:		# pc 값이 key값보다 클 때
            pr = pc
            pc_index = int((pr - pl) // 2)
            pc = a[pc_index]

        if pl > pr:
            break
            return -1
        return pc

복잡도

 

알고리즘의 성능을 객관적으로 평가하는 기준. 복잡도는 크게 시간복잡도와 공간복잡도 두가지로 나뉜다. 이 전에 공부했었던 '파이썬 알고리즘 인터뷰' 책에서 나온 빅오와 같다고 생각한다. → https://re-hwi.tistory.com/64 

 

• 시간 복잡도

: 실행하는데 필요한 시간을 평가

 

• 공간 복잡도

: 메모리와 파일 공간이 얼마나 필요하지를 평가