Algorithm/Binary Search
-
[알고리즘/Algorithm] 파이썬으로 이진 탐색 (Binary Search) 알아보기Algorithm/Binary Search 2021. 7. 6. 17:07
이진 탐색(Binary Search)이란 정렬된(중요!!) 자료(리스트)를 반으로 나누어 가며 데이터를 탐색하는 방법 이진 탐색 흐름 ex) 위 그림과 같이 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 리스트에서 숫자 8을 찾는다! 리스트의 중간에 위치한 데이터(이하 피벗/pivot)를 확인한다. 여기서는 6 해당 피벗에 데이터(6)를 확인하고, 3가지 경우로 나뉜다. 해당 피벗 데이터가 찾는 데이터면 True를 리턴 찾는 데이터가 피벗 보다 작으면 피벗 기준 왼쪽 값들을 기준으로 재 탐색 찾는 데이터가 피벗 보다 크면 피벗 기준 오른쪽 값들을 기준으로 재 탐색 데이터를 찾을 때까지, 혹은 데이터의 개수가 1이 될 때까지 1번과 2번을 반복한다. 파이썬을 통해 구현한 이진 탐색 def..