정렬
되어 있어야 한다.logN
에 비례O(logN)
을 보장log8 = 3
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& arr, int target, int start, int end) // 기존 벡터를 복사하지 않고 포인터로 참조하여 시간 복잡도 감소시킴
{
while (end >= start)
{
// 시작점과 끝점의 가운데를 중간점으로 설정
// mid = (start + end) / 2로 하면 안 됨.
// 오버플로우 발생 가능성 & start + end가 음수일 경우 결과가 달라짐.
int mid = start + (end - start) / 2;
// 설정된 중간점이 찾고자 하는 값이라면 해당 지점 반환
if (target == arr[mid]) return mid;
// 찾고자 하는 값이 중간점보다 작다면 끝점을 중간점의 왼쪽으로 옮김.
else if (target < arr[mid]) end = mid - 1;
// 찾고자 하는 값이 중간점보다 크다면 시작점을 중간점의 오른쪽으로 옮김.
else start = mid + 1;
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(); cout.tie();
int n, target;
vector<int> arr;
cin >> n >> target;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
arr.push_back(x);
}
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1)
cout << "원소가 존재하지 않습니다." << '\n';
else
cout << "Index : " << result << '\n';
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int>& arr, int target, int start, int end)
{
if (start > end) return -1;
int mid = start + (end - start) / 2;
if (target == arr[mid])
return mid;
else
{
if (target < arr[mid])
return binarySearch(arr, target, start, mid - 1); // 그냥 실행시키는 것이 아니고 return 해줘야 함.
else
return binarySearch(arr, target, mid + 1, end);
}
}
// main()은 위와 동일
: 찾고자 하는 값 이상
이 처음 나타나는 위치를 찾는 방법
int lowerBound(int arr[], int start, int end, int target)
{
int mid;
while (end > start) // end가 start보다 작거나 같게되면 멈춤
{
mid = start + (end - start) / 2;
if (target <= arr[mid]) // 중간점이 찾고자 하는 값보다 크거나 같으면 end = 중간점의 값으로
end = mid;
else if (target > arr[mid]) // 중간점이 찾고자 하는 값보다 작으면 start = 중간점 + 1
start = mid + 1;
}
if(arr[end] < target) // arr의 모든 값이 target보다 작다면 (target 이상 값 X) -1 반환
return -1;
return end;
}
: 찾고자 하는 값을 초과
하는 값이 처음으로 나타나는 위치를 찾는 방법
int upperBound(int arr[], int start, int end, int target)
{
int mid;
while (end > start)
{
mid = start + (end - start) / 2;
if (target < arr[mid]) // 중간점이 찾고자 하는 값보다 크면 end = 중간점의 값으로
end = mid;
else if(target >= arr[mid]) // 중간점이 찾고자 하는 값보다 작거나 같으면 start = 중간점 + 1
start = mid + 1;
}
if (arr[end] <= target) // arr의 모든 값이 target보다 작거나 같다면 (target 초과 값 X) -1 반환
return -1;
return end;
}
: arr 안에서 key 이상의 값이 처음으로 등장하는 위치를 반환
vector<int> arr = {1, 2, 3, 4, 5, 6, 7}
cout << lower_bound(arr.begin(), arr.end(), 6) - arr.begin();
// 출력 결과 : 5 (6의 인덱스)
: arr 안에서 key를 초과하는 값이 처음으로 등장하는 위치를 반환
vector<int> arr = {1, 2, 3, 4, 5, 6, 7}
cout << lower_bound(arr.begin(), arr.end(), 3) - arr.begin();
// 출력 결과 : 3 (4의 인덱스)
두 함수의 반환값은 모두 iterator
이기 때문에 인덱스 값을 얻고 싶으면 함수의 결과값에서 해당 배열의 시작 iterator인 arr.begin()
을 빼줘야 한다.
👁️🗨️ 참조
유튜브 동빈나(https://youtu.be/94RC-DsGMLo)
https://jackpot53.tistory.com/33
https://chanhuiseok.github.io/posts/algo-55/