코딩테스트/기본 알고리즘
2022. 2. 20.
이진탐색(Binary_Search)
Binary_Search(이진 탐색) 1. Binary_Search란 배열의 내부 데이터가 정렬되어 있어야 사용가능한 알고리즘으로 조건만 맞다면 매우 빠르다. (O(logn)의 시간복잡도) 데이터를 절반씩 좁혀가므로 위치를 나타내는 변수 (시작점, 중간점, 끝점) 3개가 필요하다. 찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교하는것이 진행방식이다. 2. 예시코드 2.1 재귀함수 방식 def binary_search(array, target, start, end): if start > end: # array에 target값이 존재하지 않아 계속된 재귀함수 호출로 start > end가 된경우 None return return None mid = (start + end) // 2 # 중간점 if ..