![]()
#0. 개념 1. 이분 탐색? [정의] : 이분 탐색은 정렬된 배열에서 특정 값을 찾기위해 사용되는 탐색 알고리즘입니다. [동작 방식] 1. 먼저, 배열의 왼쪽 경계와 오른쪽 경계를 설정합니다. 2. 중간 값을 얻어 찾고자하는 특정 값과 그 크기를 비교합니다. 3. 위 비교 연산의 결과에 따라서 왼쪽 경계 혹은 오른쪽 경계를 변경합니다. 4. 위 작업을 반복하며, 최종적으로 특정 값을 찾아냅니다. * 주의할 점 : 이분 탐색은 '정렬된' 배열에 사용되는 탐색 알고리즘입니다. 2. 코드 int BinarySearch(vector v, int l, int r, int x) { while (l x) r = mid - 1; // 찾고자 하는 값이 중간값보다 큰 경우, 오른쪽 배열 탐색 else l = mid +..
![]()
[BOJ 알고리즘, C++] #10815_숫자 카드, 이진 탐색, Binary Search BOJ 알고리즘 문제 풀이, 10815_숫자 카드 이분 탐색을 통해 주어진 숫자 카드가 존재하는지 탐색합니다. Overview 문제 풀이 코드 #1. 문제 #2. 풀이 1. 이진 탐색(Binary Search) Details [정의] : 정렬된 원소 목록을 반으로 나누어 찾고자 하는 원소와 중심이 되는 원소를 비교하고, 작다면 왼쪽으로 크다면 오른쪽으로 중심 원소를 옮겨서 반복적으로 비교 작업을 수행합니다. 시간 복잡도는 O(log n)으로 선형 탐색보다 뛰어난 성능을 보여줍니다! 다만 몇 가지 단점들이 물론 존재합니다! [특징] : 정렬 상태의 자료구조에서만 가능합니다. 그리고, 연결 리스트에서 사용이 힘듭니다...
