자료구조 - 검색

 

 

 

1. 순차검색

- 배열이 정렬되어 있지 않거나, 연결 리스트와 같이 입력이 동적으로 할당되는 경우 사용 

 

* 배열이 정리 안되어 있을 때 

import pytest
 
 
def sequential_search(seq,n):
    for item in seq:
        if item == n:
            return True
 
    return False
 
 
 
def test_sequential_search():
    seq = [1,5,6,8,3]
    n1 = 5
    n2 = 7
    assert(sequential_search(seq,n1) is True)
    assert(sequential_search(seq,n2) is False)
 
 
if __name__ == "__main__":
    test_sequential_search()
 
 

 

============================= test session starts ============================= platform win32 -- Python 3.6.9, pytest-5.2.0, py-1.8.0, pluggy-0.13.0 rootdir: F:\python_code\highperformancepythoncollected 1 item ch_10.py .테스트통과!                                                                 [100%] ============================== 1 passed in 0.02s ==============================

 

<NOTE> 

- 파이썬 구문에서 if 안에 return True가 맞으면 def 함수 끝네 return False라고 해도 True로 반환된다.

 

 

 

 

 

 

*배열 정리 되었을 때 

 

import pytest
 
 
def sequential_search(seq,n):
    for item in seq:
 
        if item >  n:
           return False
 
        if item == n:
            return True
 
    return False
 
 
 
def test_sequential_search():
    seq = [1,2,4,5,6,8,10]
    n1 = 10
    n2 = 7
    assert(sequential_search(seq,n1) is True)
    assert(sequential_search(seq,n2) is False)
    print("테스트통과! ")
 
 
if __name__ == "__main__":
    test_sequential_search()
 
 

 

#재귀함수
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
 
 
 
def test_binary_search():
    seq = [1,2,5,6,7,10,12,12,14,15]
    target = 6
    assert(binary_search_iter(seq,target) == 3)
    assert(binary_search_rec(seq,target,0,len(seq)) == 3)
    print("테스트 통과 ")
 
 
if __name__ == "__main__":
    test_binary_search()

 

<NOTE>

* 재귀함수의 장단점

장점	단점
1. 가독성이 좋다 2. 변수 사용을 줄여준다.	1. 메모리를 많이 차지하며 성능이 반복문에 비해 느림 - 재귀 함수 사용시 함수를 반복적으로 호출하기 때문에 스택 메모리가 커지고, 호출하는 횟수가 많아지면 스택오버플로우 발생

 

 

2.1 bisect 모듈

- 파이썬의 내장 bisect 모듈로 이진 검색을 할 수 있음 

from bisect import bisect
l = [0,3,4,5]
print(bisect(l,5)) #4 
 

 

<출처> 

1. 재귀함수를 쓰는 이유 - 블로그 

2. 파이썬 자료구조와 알고리즘, 미아스타인