[알고리즘] 탐색

원하는 값 얻기위해 탐색한다.

 

[1,2,3,4,5,6,7,8,9,10]

 

 

선형 탐색 알고리즘

하나하나 보는 것을 선형탐색이라고함.

 

 

이진 탐색 알고리즘

중간값을 찾아서 찾으려는 값이 왼쪽인지 오른쪽인지 확인 후

찾으려는 값이 오른쪽에 있다면 왼쪽에 있는 값 제외, 오른쪽의 값만 본다.

다시 오른쪽의 값을 가지고 위와 같이 중간값을 찾은 후 찾으려는 값이 왼쪽, 오른쪽인지 확인을 반복하면

원하는 값을 찾을 수 있다.

반씩 제외하면서 찾는 방식이다. 

 

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1
    
    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2
        if some_list[midpoint] == element:
            return midpoint
        elif some_list[midpoint] > element:
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1
    return None

some_list = [1,2,3,4,5,6,7,8,9,10] 가 있다고 할 때 이진 탐색 알고리즘으로 element = 9를 찾으려고 한다.

 

start_index와 end_index로 리스트의 처음과 마지막을 선언해주고

while문 안에서 중간index를 구해준다. midpoint = 4

midindex를 이용하여 구한 값이 element 값과 비교후 같다면 찾고있는 값을 return하고

중간을 구한 값이 element 보다 크다면 찾는 값은 중간 값보다 왼쪽에 있고

element 보다 중간값이 작다면 오른쪽에 위치하고 있다.

some_list[midpoint] = 5, element = 9 이므로 else 로가서 start_index가 5이 된다.

다시 돌아가서 midpoint = (5+9)//2 가 되므로 midpoint는 7이된다.

위와 같은 if 문을 반복하면 element의 값을 찾게된다.

 

단 리스트는 정렬이 되어있어야한다.

 

최적 : O(1)

최악: O(lg n)  범위가 반씩 줄어들어서

 

 

선형탐색과 이진탐색 중 뭐가 더 괜찮?

선형탐색은 리스트가 길어질수록 걸리는 시간이 급격하게 커짐

이진탐색은 리스트가 길어져도 걸리는 시간이 천천히 늘어남

 

단 이진탐색을 사용하기 위해선 리스트가 정렬이 되어있어햐 한다.

정렬이 되지 않으면 선형탐색을 사용해야함