[TIL] 100. [알고리즘] 탐색

키워드

• 탐색
• 선형탐색
• 이진탐색

[알고리즘] 탐색

• 자료를 하나씩 탐색하는 알고리즘
• 문제를 해결하기 위해서는 문제를 탐색해야한다.

[탐색] 선형탐색(Linear Search)

• 기본적인 탐색 알고리즘으로 한번에 하나씩 차근차근 모두 검색하는 것

def linear_search(arr, value):
    for i in range(len(arr)):
        if arr[i] == value:
            return i

[탐색] 이진탐색(Binary Search)

• 탐색을 할 때, 반씩 줄여나가면서 탐색
• 마치 업다운 게임에서 가운데 값을 말하면 점점 좁혀나가는 방식
• 단, 데이터가 이미 정렬된 경우에만 작동한다.
• O(logn)의 시간복잡도를 갖는다.(그룹을 2개씩 나누면서 진행하기 때문)

def binary_search(arr, value):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == value:
            return mid
        elif arr[mid] < value:
            low = mid + 1
        else:
            high = mid - 1
    return '인덱스 없음' # 값을 찾지못한 경우