[Algorithm] Search Algorithm
in Computer Science on Algorithm
Search Algorithm 탐색 알고리즘
- 탐색은 여러 데이터 중 원하는 데이터를 찾아내는 것을 의미함
- 검색 엔진에 탐색 알고리즘이 많이 사용되기도 함 (그래서 검색 알고리즘이라고도 함)
Sequential Search Algorithm 순차 탐색 알고리즘
- 리스트의 가장 처음부터 시작하여 찾으려는 데이터가 나올 때까지 하나씩 리스트의 각 요소와 비교하는 탐색 알고리즘
- Linear Search Algorithm (선형 탐색 알고리즘)이라고 하기도 함
- O(n)의 시간 복잡도를 가짐
def sequencial_Search(data_list, search_data):
for index in range(len(data_list)):
if data_list[index] == search_data:
return True
return False
Binary Search Algorithm 이진 탐색 알고리즘
- 찾으려는 데이터가 나올 때까지 탐색할 리스트를 둘로 나누어가며 탐색 하는 알고리즘
- 이진 탐색은 반드시 리스트가 정렬되어 있는 상태에서 탐색을 진행
- O(nlogn)의 시간 복잡도를 가짐
def binary_search(data, search):
data.sort() # 리스트 정렬 필수
if len(data) == 1 and search == data[0]:
return True
if len(data) == 1 and search != data[0]:
return False
if len(data) == 0:
return False
medium = len(data) // 2
if search == data[medium]:
return True
else:
if search > data[medium]:
return binary_search(data[medium+1:], search)
else:
return binary_search(data[:medium], search)
순차 탐색 vs 이진 탐색
- O(n)의 시간 복잡도를 가지는 순차 탐색과 O(nlogn)의 시간 복잡도를 가지는 이진 탐색의 연산 속도는 데이터의 양이 많아지면 많아질 수록 속도의 차이가 커짐
