알고리즘(탐색)

순차 탐색: 정렬되지 않은 배열에 적용 가능

정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사

가장 간단하고 직접적인 탐색방법

평균 비교 횟수: (n+1)/2번 비교 (최악의 경우: n번)

def sequential_search(A,key,low,high):
    for i in range(low, high+1):
        if A[i].key == key:
            return 1
    return None

이진 탐색: 정렬된 배열의 탐색에 적합

배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄여가며 탐색 진행 ex) 업다운 게임

def binary_search(A,key,low,high):
    if(low<=high):
        middle = (low + high)//2
        if key ==A[middle].key:
            return middle
        elif (key<A[middle].key):
            return binary_search(A,key,low,middle-1)
        else:
            return binary_search(A,key,middle+1,high)
    return None

해싱

키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산

해시 테이블

키 값의 연산에 의해 직접 접근이 가능한 구조

해시 함수

탐색키를 입력받아 해시 주소 생성