이진탐색/선형탐색

Search 알고리즘

 

1) 선형탐색 O(N)

선형탐색 이란 일렬로 된 자료를 왼쪽부터 차례대로 탐색하는 것을 말한다 

즉 배열이 커질수록 시간이 길어지며 시간복잡도는 O(N) 을 이룬다

인풋이 많을수록 수행하는 시간또한 선형적으로 증가하게 된다.

 

구현이 아주 쉽다는 장접이 있지만 시간 복잡도가 O(N) 이라서 효율적이지 않다는 단점이 있다.

def solution(L, x):
    for i in range(len(L)):
        if x == L[i]:
            return i
    return -1

L1 = [3,5,2,8,6,1,7]
x = 2
y = 7

print(solution(L1, x))
print(solution(L1, y))

# 선형탐색 예제
# 2 6 출력

 

여기서 발전한 방법이 이진탐색이다.

 

 

1) 이진탐색 O(log N)

이진탐색 이란 오름차순으로 정렬 된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

정렬 된 리스트란 순서대로 정렬된것, 크기순도, 가능하다



처음 중간의 값을 임의의 값으로 선택하여 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식이다.

처음 선택한 중앙값이 찾는 값보다 크면 그 값이 최댓값이 되며 작으면 새로운 최솟값이 된다.

 

def solution(L,x):
    upper = len(L) - 1
    lower = 0
    while upper >= lower:
        mid = (upper + lower) // 2
        if x == L[mid]:
            return mid
        elif x < L[mid]:
            upper = mid - 1
        else:
            lower = mid + 1
    return -1

L1 = [1,3,5,7,9,11]
x1 = 3
x2 = 7
print(solution(L1, x1))
print(solution(L1, x2))

# 이진 탐색 예제
# 1 3 출력

 

예제 출처:https://growingsaja.tistory.com/483