탐색 알고리즘

1. 선형 탐색

def linear_search(L,value):
    for i in L:
        if i == value:
            return True
    return False

 

2. 이진탐색 

※ 전제조건 : 정렬된 이더레이터에 적용

def binary_searh(L: list, n: str) -> int:
    """
    from bisect import bisect_left 구현

        Args:
            L (list): 검색 대상
            n (str): 검색 내용

        Returns:
            int: index 반환
    """

    first = 0
    last = len(L) - 1
    while last >= first:
        mid = (first + last) // 2
        if L[mid] == n:
            return mid
        else:
            if n < L[mid]:
                last = mid - 1
            else:
                first = mid + 1
    return mid


sorted_fruits = ["apple", "banana", "orange", "plum"]
a = binary_searh(sorted_fruits, "kiwi")
print(a)

 

 

# 문자 탐색

def binary_search(a_list, c):
    first = 0
    last = len(a_list) - 1
    target_code = ord(c)
    while last >= first:
        mid = (first + last)//2
        if a_list[mid] == c:
            return True
        else:
            if target_code > ord(a_list[mid]):
                first = mid + 1
            else:
                last = mid - 1

    return False

print(binary_search(['a', 'b', 'c', 'd'], 'b'))