3.탐색 알고리즘(Search Algorithm)

 

1.선형탐색(조건X) - O(n)

def LinearSearch(arr,target):

    for i in range(len(arr)):

        if arr[i] == target:

            return i

    return 'Data Not Found'

1번째부터 n번째까지 순차적으로 비교해가면서 탐색하는 방법. 시간복잡도는 O(n)이다.

2.이진탐색(조건:정렬O) - O(logn)

def BinarySearch(arr,target):

    buttom = 0

    top = len(arr)-1

    while buttom <= top:

        mid = int((buttom+top)/2)

        if arr[mid] == target:

            return mid

        elif arr[mid] < target:

            buttom = mid+1

        else:

            top = mid-1

    return 'Data Not Found'

정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다. 탐색 영역을 반으로 줄여가면서 찾는방법이다.

시간복잡도는 O(logn) 이다.