Linear search & Binary search

0번부터 7번까지 총 8개의 상자가 있다. 근데 A는 이 상자중에 10000원이 들어있는 상자를 찾고싶다. 어떤 방법으로 찾아야 할까?

A는 원하는 상자를 2가지 탐색방법으로 찾을것이다. 바로 선형탐색과 이진탐색이다.

선형탐색

• 선형탐색은 위의 상자를 0번부터 7번까지 순차적으로 탐색하는 것을 말한다.

• 순차적으로 탐색하므로 정리되어있지 않은 자료라도 사용가능한 방법이다.

• 선형탐색 알고리즘

    def linear(box, find):
        for i in range(len(box)):
            if box[i] == find:
                return i
        
        return None
        
    box = [5000, 10, 1, 50000, 1000, 50, 10000, 100]
    find = int(input('찾는 값을 입력하세요: '))

    print(linear(box, find))

이진탐색

• 정렬되어있는 데이터 중 특정 값을 찾아내는 방법이다.

• 선형탐색보다 탐색시간이 빠르지만 정렬되어있지 않다면 사용할수 없다.

• 시간복잡도 O(log n)

• 이진탐색 방법

우선 상자를 크기순으로 정렬한다.

중앙의 3번 상자와 6번 상자를 비교해보면, 3번 상자의 금액보다 6번 상자의 금액이 더 크다.

6번 상자의 금액이 3번 상자의 금액보다 크므로 3번 상자의 금액보다 적은 금액은 비교할 필요가 없다.

3번 상자보다 큰 금액이 들어있는 상자중에 중앙값(5번 상자)을 선정한다.

중앙값인 5번 상자의 금액보다 6번 상자의 금액이 더 크므로 다시 중앙값을 구한다.

중앙값이 6번상자가 되므로 원하는 금액을 찾게된다.

• 이진탐색 알고리즘

    def binary(find, box):
        first = 0
        last = len(box) - 1

        while first <= last:
            mid = (first + last) // 2
            
            if box[mid] == find:
                return mid
            
            elif box[mid] < find:
                first = mid + 1
                
            elif box[mid] > find:
                last = mid - 1
                
        return None

    box = [5000, 10, 1, 50000, 1000, 50, 10000, 100]
    box.sort() # 상자정렬
    find = int(input('찾는 값을 입력하세요: '))

    print(binary(find, box))

• 이진탐색 재귀적 알고리즘

    def binary(first, last, find, box):
    
        if first > last:
            return None
    
        mid = (first + last) // 2
    
        if box[mid] == find:
            return mid
        
        elif box[mid] < find:
            return binary(mid + 1, last, find, box)
        
        elif box[mid] > find:
            return binary(first, mid - 1, find, box)

    box = [5000, 10, 1, 50000, 1000, 50, 10000, 100]
    box.sort()
    first = 0
    last = len(box) - 1
    find = int(input('입력: '))

    print(binary(first, last, find, box))