[알고리즘] 검색 알고리즘2

1. 이진 검색

이진검색이란?

데이터를 두 부류로 나눈 뒤 조건을 만족하는 쪽 데이터에만 동일한 과정을 반복해 나가는 방식을 이진검색이라고 합니다.

이진 검색은 데이터가 크기 순서로 나열되어 있을 때 사용합니다. 선형 검색보다 계산량이 적어서 더 짧은 시간에 원하는 데이터를 찾을 수 있습니다.

이진 검색 예시 코딩

a = ['bear', 'cat', 'dog', 'lion', 'panda', 'tiger']

다음과 같이 알파벳 순으로 놓인 배열을 만들었습니다.
여기서 이진 검색 방법으로 dog를 찾아보겠습니다.

a = ['bear', 'cat', 'dog', 'lion', 'panda', 'tiger']

# 찾고 싶은 동물 입력
find_val = input("what kind of animal you want to find? ")

count = 0 # 검색횟수
front = 0 # 이진검색 시 맨 앞 index
mid = divmod(len(a), 2)[0] # 이진검색 시 중간 index
end = len(a) # 이진검색 시 맨 끝 index


while True:
    find = 0
    mid_val = a[mid] # 중간값
    print(mid_val)
    i = mid_val[0] # 맨 앞 글자를 비교
    count = count + 1
    if ord(i) < ord(find_val[0]):
        front = mid
    elif ord(i) > ord(find_val[0]):
        end = mid
    elif ord(i) == ord(find_val[0]):
        print("Find!!", count, "times try!!")
        find = 1
    mid = divmod(front + end, 2)[0]
    if find == 1: # 원하는 값을 찾으면 while문 탈출
        break

코드를 실제로 실행하여 확인해보면

다음과 같이 잘 실행되는 것을 확인할 수 있습니다. dog 외 다른 값을 입력해도 모두 잘 수행되는것을 확인할 수 있습니다.

이진 검색에서는 데이터가 n가 있을 경우 log n번(소수점이 있을 경우 올림으로 정수로 변환) 조사해야하여 최대 시간 복잡도가 O(log n)입니다.

선형 검색의 경우 최대 n번의 조사를 해야하여 최대 시간 복잡도가 O(n)이고 이진 행렬의 경우 이보다 시간 복잡도가 작기 때문에 데이터가 크기 순으로 정렬되어 있을 경우 이진행렬을 사용하는것이 더 좋습니다.