자료구조,알고리즘 (1) 썸네일형 리스트형 순차탐색(sequential search), 이진탐색(binary search) 순차탐색 : 말 그대로 순차적으로 모든 데이터들을 확인하면서 탐색하는 방법 : list내에 특정 원소를 찾는 경우, 원소의 개수를 세는 경우 : 시간복잡도 O(n), 최악의 경우 모든 원소를 다 확인해야 하기에 이진탐색 : binary search : "정렬된 데이터"임을 전제로 사용할 수 있는 방법 : 탐색범위를 절반으로 좁혀가면서 탐색할 수 있는 방법 : O(logn)의 시간복잡도 -- 데이터 개수가 2배 늘어날 때, 탐색 횟수가 한 번 증가한다 -- W(2^k) = k+1 , W(k) = logn +1 python을 바탕으로 한 이진탐색의 구현 - 재귀, 반복 두 가지 방법 존재 import sys #반복문을 통한 구현 def binary_search_1(data, n, target): low, h.. 이전 1 다음