탐색 알고리즘

탐색 알고리즘의 종류

1. 완전탐색( Brute force )

모든 경우의 수를 탐색하는 방법이다. 굉장히 직관적이고 놓치는 값 없이 탐색을 진행할 수 있다는 장점이 있지만, 경우의 수가 많아질 수록 탐색시간이 늘어나 비효율적인 방식이 된다.

2. 이진탐색

사람들이 즐기는 업앤다운 게임을 생각하면 이해하기 쉽다. 업앤다운 게임은 출제자가 숫자 하나를 선정하면 나머지 사람들은 숫자를 유추하고 출제자는 유추한 숫자가 선정된 숫자보다 작은지 큰지를 알려주며 점점 범위를 좁혀나가 숫자를 알아맞추는 게임이다. 이진탐색도 마찬가지로 정렬된 숫자배열에서 중간값을 찾고 찾으려는 값이 중간값보다 작은지 큰지를 비교하며 점점 범위를 좁혀나가며 숫자를 찾는 방식이다.

• 이진탐색코드예제

# 1~10까지 순서대로 담긴 list가 존재하고 여기서 8을 찾아내는 이진탐색 코드
def solution(list):
    left=0
    right=len(list)-1
    while(left<=right):
        mid=(left+right)//2
        if list[mid]==8:
            return mid
        elif list[mid]<8:
            left=mid+1
        elif list[mid]>8:
            right=mid-1
    return mid