[CodeKata] -20

김가람휘·2022년 3월 8일
0

CodeKata

목록 보기
20/28


def search(nums, target):
    start = 0
    end = len(nums)-1

    while start <= end:
        center = (start+end)//2
        if nums[center] == target:
            return center
        elif nums[center] > target:
            end = center-1
        else:
            start = center+1

    return -1
def binary_search_recursion(target, start, end, data):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1

    return binary_search_recursion(target, start, end, data)

if __name__ == '__main__': # 메인 함수 선언
    my_list = [i*3 for i in range(11)]
    target = 9
    my_index = binary_search_recursion(target, 0, 10, my_list)

    print(my_list)
    print(my_index)
  • 이진탐색법의 시간 복잡도

    • 처음에 데이터 수가 n개일 때의 탐색과정에서 1회의 비교연산 진행
    • 데이터 수를 반으로 줄여서 그 수가 n/2개일 때의 탐색과정에서 1회 비교연산 진행
    • 데이터 수를 반으로 줄여서 그 수가 n/4개일 때의 탐색과정에서 1회 비교연산 진행
    • 데이터 수를 반으로 줄여서 그 수가 n/8개일 때의 탐색과정에서 1회 비교연산 진행
      ..........
    • 데이터 수를 반으로 줄여서 그 수가 1개일 때의 탐색과정에서 1회 비교연산 진행
      -> n이 1이 되기까지 2로 나눈횟누는 k회
      -> 데이터가 1개 남았을 때, 마지막으로 비교연산을 진행해서 1회 진행
      n(12)k=1n * (\frac{1}{2})^k=1
      -> n2k=1n * 2^-k=1
      -> n=2kn = 2^k
      -> log2n=log22k\log_2 n = \log_2 2^k
      -> log2n=k\log_2 n = k
      • 시간복잡도 : T(n)=log2n+1T(n) = \log_2 n + 1
        -> 1은 생략 가능
        -> T(n)=log2nT(n) = \log_2 n

0개의 댓글