[c++] 이진 탐색 알고리즘 활용
목차
1. 이진 탐색 알고리즘이란?
이진 탐색 알고리즘(Binary Search Algorithm) 은 정렬된 배열에서 특정 원소를 찾는 알고리즘으로, 배열의 중간 값과 목표 값을 비교하여 해당 값이 중간 값의 좌측 또는 우측 배열에 위치하는지를 확인하고, 탐색 범위를 반으로 줄여가면서 원하는 값의 위치를 찾아냅니다. 이 알고리즘은 배열 내의 탐색 시간을 절반으로 줄여주는 장점이 있습니다.
2. 이진 탐색 알고리즘의 예시
다음은 C++의 코드 예시입니다.
#include <iostream>
#include <vector>
#include <algorithm>
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 타겟이 배열에 없을 경우
}
int main() {
std::vector<int> nums = {2, 5, 7, 10, 15, 20};
int target = 7;
int result = binarySearch(nums, target);
if (result != -1) {
std::cout << "원소 " << target << "는 인덱스 " << result << "에 있습니다." << std::endl;
} else {
std::cout << "원소 " << target << "를 찾을 수 없습니다." << std::endl;
}
return 0;
}
3. 이진 탐색 알고리즘의 구현
이 코드는 정렬된 배열 nums에서 target 값을 찾는 이진 탐색 알고리즘의 구현 예시입니다. 이진 탐색 알고리즘을 통해 배열 내에서 효율적으로 원소를 찾을 수 있습니다.