반응형
개념
이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.
https://blog.hexabrain.net/246 참고
알고리즘 2-2강. 탐색 알고리즘 - 이진 탐색(Binary Search)
[탐색 알고리즘 강좌] 데이터를 찾아보자! 이진 탐색(Binary Search) 이번에는 순차 탐색에 이어 이진 탐색(Binary Search)에 대해 알아보도록 할텐데, 이 '이진 탐색(Binary Search)'이 왜 이진인지 짐작이 가
blog.hexabrain.net
조건
- 수들이 오름차순 또는 내림차순으로 정렬 되어 있어야 한다.
- 원하는 값을 찾으면 종료한다. (종료 조건1) → 값을 찾음
- 왼쪽값이 오른쪽 값보다 커지면 종료한다. (종료조건2) → 값이 없음
사용 하면 좋은 경우
- 리스트에서 값을 찾을 때 시간을 단축해야 하는 경우
- list에서 find() 함수를 사용하거나 반목문으로 값을 찾을 시 O(N)의 시간이 필요하기 때문에 이진 탐색을 사용하면 시간 효율성을 증가 시킨다.
- 조건에 맞는 최소 또는 최대값을 찾아야 하는 경우
- 이러한 경우에는 index를 left, right로 두지 않고 left = 가장 작은 값, right = 가장 큰 값 으로 설정하여 배열에서의 위치가 아닌 조건에 맞는 값을 구 할 수 있도록 한다.
구현 방법
기본 이진 탐색
- 반복문
#include <iostream>
#include <vector>
using namespace std;
int BinarySearch(vector<int> num, int target) {
int left = 0, right =(int) num.size(), mid = 0;
sort(num.begin(), num.end()); //숫자 오름차순 정렬
//num : {1, 2, 4, 5, 15, 56, 123, 125, 199, 3215}
while(left <= right) { //종료 조건
mid = (left + right) / 2;
if(num[mid] == target) {// target을 찾았을 때
return mid;
}
else if(num[mid] > target) { //target보다 클 때 -> 왼쪽 수들을 확인
right = mid - 1;
}
else { //target보다 작을 때 -> 오른쪽 수들을 확인
left = mid + 1;
}
}
return -1;
}
- 재귀 함수
#include <iostream>
#include <vector>
using namespace std;
//재귀 함수는 num을 정렬 해서 함수 호출
int RecurBinarySearch(vector<int> num, int target, int left, int right) {
if(left > right) return -1; //종료 조건
int mid = (left + right) / 2;
if(num[mid] == target) { //target을 찾았을 때
return mid;
}
else if(num[mid] > target) { // target보다 클 때
return RecurBinarySearch(num, target, left, mid-1);
}
else { //target보다 작을 때
return RecurBinarySearch(num, target, mid+1, right);
}
}
int main(int argc, const char * argv[]) {
vector<int> num {1,5,2,199,56,3215,125,123,15,4};
sort(num.begin(), num.end());
int left = 0, right = (int)num.size();
cout << RecurBinarySearch(num, 199, left, right) << endl;
return 0;
}
UpperBound
목표값보다 큰 값이 처음 발견되는 곳 찾기
int UpperBound(vector<int> num, int target) {
int left = 0, right = (int) num.size(), mid = 0;
sort(num.begin(), num.end());
int ans = 0;
while(left <= right) {
mid = (left + right) / 2;
if(num[mid] <= target) { // 목표보다 작거나 같으면 오른쪽 보기
left = mid + 1;
}
else { // 목표보다 크면 답의 후보로 두고 왼쪽 보기
ans = mid;
right = mid - 1;
}
}
return ans;
}
LowerBound
목표값보다 작은 값이 처음 발견되는 곳 찾기
int LowerBound(vector<int> num, int target) {
int left = 0, right = (int) num.size(), mid = 0;
sort(num.begin(), num.end());
int ans = 0;
while(left <= right) {
mid = (left + right) / 2;
if(num[mid] >= target) { //목표보다 크거나 같으면 왼쪽 보기
right = mid - 1;
}
else { // 목표보다 작으면 답의 후보로 두고 오른 쪽 보기
ans = mid;
left = mid + 1;
}
}
return ans;
}
결과
int main(int argc, const char * argv[]) {
vector<int> num {1,5,2,199,56,3215,125,123,15,4};
sort(num.begin(), num.end());
int left = 0, right = (int)num.size();
for(int i = 0; i < num.size(); i++) {
cout << num[i] << " ";
}
cout << endl;
cout << "재귀 : " << RecurBinarySearch(num, 199, left, right) << endl;
cout << "반복문 : " << BinarySearch(num, 199) << endl;
cout << "UpperBound : " << UpperBound(num, 199) << endl;
cout << "LowerBound : " << LowerBound(num, 199) << endl;
return 0;
}
| 1 2 4 5 15 56 123 125 199 3215 재귀 : 8 반복문 : 8 UpperBound : 9 LowerBound : 9 |
시간 복잡도
- O(logN)
반응형
'코딩 낙서' 카테고리의 다른 글
| 알고리즘 - 크루스칼(Kruskal) (0) | 2023.06.21 |
|---|---|
| 알고리즘 - 누적합(Prefix Sum) (0) | 2023.06.21 |
| 알고리즘 - Union & Find (0) | 2023.06.21 |
| [LINUX] 기본 명령어 정리 (0) | 2023.06.20 |
| Linux (0) | 2023.06.14 |
