반응형 [C++로 배우는 알고리즘과 자료구조] Day 22: 이진 탐색 (Binary Search) 이진 탐색 (Binary Search)이진 탐색은 정렬된 배열에서 원하는 값을 찾는 효율적인 알고리즘입니다. 배열의 중간 값을 선택하고, 중간 값과 찾고자 하는 값을 비교하여 검색 범위를 절반으로 줄여가며 탐색합니다.이진 탐색의 시간 복잡도:최선의 경우: (O(1))평균의 경우: (O(\log n))최악의 경우: (O(\log n))이진 탐색 구현이진 탐색은 재귀적으로 또는 반복적으로 구현할 수 있습니다. 재귀적 이진 탐색 구현#include #include // 재귀적 이진 탐색 함수int binarySearchRecursive(const std::vector& arr, int left, int right, int target) { if (right >= left) { int mid .. 2024. 8. 1. [알고리즘] 6. 이진 탐색 Index 1. 순차 탐색 2. 이진 탐색 3. 이진 탐색 라이브러리 4. 파라메트릭 서치 5. 추천 문제 6. 참고자료1. 순차 탐색순차 탐색(Sequential Search)- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 2. 이진 탐색이진 탐색(Binary Search)- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법- O(log N) (재귀적 구현)def binary_search(arr, target, start, end): if start > end: return None mid = (start + end) // 2 if arr[mid] == target: return mid elif arr[mid] > target: re.. 2024. 7. 19. 이전 1 다음 반응형
