728x90 반응형 이진탐색1 알고리즘 - 이진 탐색 (Binary Search) 알고리즘 - 이진 탐색 (Binary Search) 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘으로, 모든 값을 순회해야하는 일반적인 search보다 더 빠르다. 중앙값을 찾는 값에 비교해서 중앙값이 찾는 값보다 크면 왼쪽을 탐색하고 찾는 값보다 작으면 오른쪽을 탐색한다. 최악의 경우에도 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, 탐색 횟수가 logN이다. 따라서 T(N) = O(logN) [ 예시 ] [ 코드 ] def binary_search(arr, target): low, high = 0, len(arr) - 1 while low target: high = mid - 1 if arr[mid] == target: return mid if arr[mid] < target: l.. 2021. 1. 26. 이전 1 다음 728x90 반응형
