검색 알고리즘(순차 검색, 이진 검색)

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 알고리즘 내용입니다

목차

• 정렬되지 않은 배열 - 순차 검색(Linear Search)
• 정렬된 배열 - 이진 검색(Binary Search)

 

<검색>

리스트가 정렬되어 있다고 할 때, 이진 검색(binary search)이 순차 검색(linear search)보다 더 효율적이다.

 

정렬되지 않은 배열

순차 검색(Linear Search)

• 순차 검색은 키(key)라는 요소를 가지고 순차적으로 리스트의 각 요소들을 비교하는 검색방법이다.
• 리스트 요소의 수가 커지면 커질수록 선형 검색 시간이 증가하므로, 큰 리스트에서는 비효율적이다. (시간복잡도 O(1),O(n/2),O(n))
• 키(key)가 찾고자 하는 요소와 일치 할 때 까지 수행을 진행하고, 매치되었다면, 순차 검색은 매칭된 요소의 위치(index)를 반환. 매치되지 않았다면, -1을 반환한다.

#리스트가 정렬되어 있지 않은 경우
def seq_search(seq,n):
    for item in seq:
        if item == n:
            return True
    retrun False
    
#리스트가 정렬되어 있는 경우
def ordered_seq_search(seq,n):
    item = 0
    for item in seq:
        if item > n:
            return False
        if item == n:
            return True
    retrun False

 

정렬된 배열

이진 검색(Binary Search)

이진 검색은 정렬된 리스트의 중간부터 비교해나가는 검색방법이다. 즉, 리스트를 반으로 나눠 검색한다.

이진검색에는 아래와 같은 3가지 경우가 존재한다.

- 입력값 = 중간값 : 배열의 위치 반환

- 입력값 < 중간값 : 중간 요소의 왼쪽 하위 배열에서 검색 반복

- 입력값 > 중간값 : 중간 요소의 오른쪽 하위 배열에서 검색 반복

※ 파이썬은 내장 bisect(리스트, 값)으로도 이진 검색이 가능하다.

# 재귀함수
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