[ 자료구조 ] 검색 알고리즘 (search algorithm)

1. 이진 검색 함수

def book_search(index_array, find_name):

    pos = -1
    start = 0
    end = len(index_array) - 1

    while start <= end:
        mid = (start + end) // 2
        if find_name == index_array[mid][0]:
            return index_array[mid][1]

        elif find_name > index_array[mid][0]:
            start = mid + 1

        else:
            end = mid - 1
    return pos

위치(pos)를 처음에 -1로 설정한다.

start≤end일 경우 계속 반복하고 mid에 start와 end의 중간값을 넣어준다.

만약 찾는 데이터와 중간값이 같을 경우 반환

찾는 데이터가 더 작을경우 end = mid - 1

찾는 데이터가 더 클경우 start = mid + 1

찾는 데이터가 존재하지 않을 경우 초기 설정한 pos값 반환 = -1

퀵 정렬과 비슷한 알고리즘 → pivot을 설정하고 분할하여 찾는 검색이다.

2. 이진검색 후 물품별로 판매 개수 리스트 반환 함수

def count_product(sell_array, sell_product):
    """
    sell_array: 판매된 물건 배열
    sell_product: 판매된 물품 종류 배열
    """
    arr = []

    for i in sell_product:
        count = 0
        while True:
            pos = binary_search(sell_array, i)
            if pos == -1:
                break
            count+=1
            del sell_array[pos]
        arr.append((i, count))

    return arr

pos를 처음에 0으로 설정해주고 i를 기준으로 이진검색을 진행한다 → pos가 -1이 아닐때까지 반복

-1이 아니면 pos위치에 있는 요소를 삭제하고 count를 증가. → 계속 반복시 pos값은 최종적으로 -1이 되고 루프 탈출

arr에 카운트와 물건 이름을 튜플로 묶어서 추가

퀵 정렬로 arr 배열 정렬

3. 순차 검색

검색할 집합이 정렬되어 있지 않은 경우 순차 검색을 해야한다.

데이터 개수가 n개일 경우 **시간 복잡도는 O(n)**이다.

4. 이진 검색

정렬된 데이터 집합에서만 가능하다.

전체를 반씩 잘라 내서 한쪽을 버리는 방식을 사용한다.

데이터 개수가 계속 1/2씩만 남으므로 급격히 비교할 데이터 개수가 줄어든다.

시간 복잡도가 **O(nlogn)**이다.