10-1. 검색 (Searching): 파이썬 자료구조와 알고리즘

 

검색 알고리즘은 배열이 정렬되어 있는 경우 순차 검색 (sequential search) 를 흔히 사용하며 정렬되어 있지 않은 경우 이진 검색 (binary search) 을 많이 사용한다. 해시 테이블은 보조 메모리 공간을 사용하지만, 키를 이용하면 O(1)에 원하는 값을 검색할 수 있다.

 

정렬되지 않은 배열 검색

순차 검색

순차 검색 (sequential search) 은 아주 당연히도 순차적으로 배열을 돌면서 해당하는 항목을 검색하는 것이다. 최선의 경우 시간 복잡도는 O(1) 이며, 평균은 O(n/2), 최악의 경우는 O(n)이다 (굉장히 당연히도). 만약 리스트에 검색하려는 항목이 없다면 최악/최선/평균 모두 O(n)이다.

 

def sequential_search(seq, n):
    for item in seq:
        if item == n:
            return True
    return False

l = [5,8,3,3,4,6,2,2,9,1]
print(sequential_search(l, 1))
print(sequential_search(l, 10))

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/10. 검색/sequential_search.py"
True
False

 

리스트가 정렬되어 있는 경우 검색하려는 항목이 없는 경우에도 최선 O(1), 평균 O(n/2), 최악 O(n)의 시간 복잡도를 갖는다.

 

빠른 선택과 순서통계량

퀵 정렬 알고리즘을 약간 수정하여 리스트에서 k번째로 작은 항목을 찾아보자.

 

import random

def quick_select_cache(seq, k):
    len_seq = len(seq)
    if len_seq < 2:
        return seq[0]
    
    ipivot = len_seq // 2
    pivot = seq[ipivot]
    smallerList = [x for i, x in enumerate(seq) if x <= pivot and i != ipivot]
    largerList = [x for i, x in enumerate(seq) if x > pivot and i != ipivot]

    m = len(smallerList)
    if k == m:
        return pivot
    elif k < m:
        return quick_select_cache(smallerList, k)
    else:
        return quick_select_cache(largerList, k-m-1)

def swap(seq, x, y):
    seq[x], seq[y] = seq[y], seq[x]

# def quick_select(seq, k, left=None, right=None):
#     left = left or 0
#     right = right or len(seq) - 1
#     ipivot = random.randint(left, right)
#     pivot = seq[ipivot]

#     swap(seq, ipivot, right)
#     swapIndex, i = left, left
#     while i < right:
#         if pivot < seq[i]:
#             swap(seq, i, swapIndex)
#             swapIndex += 1
#         i += 1
    
#     swap(seq, right, swapIndex)
    
#     rank = len(seq) - swapIndex
#     if k == rank:
#         return seq[swapIndex]
#     elif k < rank:
#         return quick_select(seq, k, swapIndex + 1, right)
#     else:
#         return quick_select(seq, k, left, swapIndex - 1)

seq = [3, 7, 2, 1, 4, 6, 5, 10, 9, 11]
k = len(seq) // 2
print(quick_select_cache(seq,0))

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/10. 검색/quick_select.py"
1

 

정렬된 배열

이진 검색

이진 검색은 정렬된 배열 내의 지정된 입력값의 위치 (키) 를 찾는다. 이진 검색은 알고리즘의 각 단계에서 입력값과 배열 중간 요소를 비교하며, 입력값과 중간 요소가 일치한다면 배열의 위치가 반환된다. 입력값이 중간 요소보다 작으면, 중간 요소의 왼쪽 하위 배열에서 검색 과정을 반복하는 식이다. 따라서 최대 배열 반복의 깊이 만큼 (log n) 반복되기 때문에, 이진 검색의 시간 복잡도는 O(log n)이다.

 

# 재귀 함수

def binary_search_rec(seq, target, low, high):
    if low > high:
        return None
    mid = (low + high) // 2
    if target == seq[mid]:
        return mid
    elif target < seq[mid]:
        return binary_search_rec(seq, target, low, mid-1)
    else:
        return binary_search_rec(seq, target, mid+1, high)

# 반복문

def binary_search_iter(seq, target):
    high, low = len(seq), 0
    while low < high:
        mid = (high + low) // 2
        if target == seq[mid]:
            return mid
        elif target < seq[mid]:
            high = mid
        else:
            low = mid + 1
    return None

l = [1,2,3,4,5,6,7,8,9,10]
target = 8
print(binary_search_rec(l, target, 0, 10)),
print(binary_search_iter(l, target))

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/10. 검색/binary_search.py"
7
7

 

출처

파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인