Written by Lee Jongseo
on May 21, 2021

Alogrithm[4]:⭐ - Linear Search, Binary Search

Searching Algorithm(검색 알고리즘)

Sequence안에 특정 target value가 있는지 없는지 알기 위한 검색 알고리즘. search: if target in data: return True else: return False

Unsorted, Sorted

어떤 검색 알고리즘을 사용할 것인지 선택할 때, Sequence가 정렬된 상태인지, 아닌지가 중요하다.

Sequence가 unsorted상태일 때, 적용할 수 있는 검색 알고리즘은 Linear Search가 있고,
Sorted 상태인 동시에 indexable일 경우, Binary Search를 적용할 수 있다.

Linear Search(순차 탐색)

단순하게 Sequence의 첫번째 요소부터 시작하여 target이 있는지 검사하는 알고리즘

def linear_search(S, target):
    for index in range(len(S)):
        if target == S[index]:
            return True
    return False

시간복잡도: O(n)

Binary Search(이진 탐색)

Sequence가 Sorted, Indexable인 경우 사용가능한 검색 알고리즘.

Recursive way

def binary_search(S, target):
    mid = len(S) // 2 # mid index
    if (S[mid] == target):
        return True
    elif (S[mid] < target):
        return binary_search(S[mid+1:], target)
    else:
        return binary_search(S[:mid], target)

검색 범위가 주어진 경우

def binary_search(S, target, low, high):
    mid = (low + high) // 2
    if (S[mid] == target):
        return True
    elif (S[mid] < target):
        return binary_search(S, target, mid+1, high)
    else:
        return binary_search(S, target, low, mid-1)

Iterative way

def binary_search(nums, target):
    left, right = 0, len(nums)-1
    while left < right:
        pivot = (left + right) // 2
        if (target == nums[pivot]):
            return True
        elif (target < nums[pivot]):
            right = pivot - 1
        else:
            left = pivot + 1
    return False

👈 👉 Top