이분 검색(binary search) in C++
6140 단어 Binary SearchBinary Search
1. 일정 숫자 배열이 주어질때, 오름차순 정렬시 특정 숫자가 몇번째에 있는지를 구하는 코드(0번째부터 시작)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
freopen("input.txt", "rt", stdin);
int n;
vector<int> V;
int want_to_find;
int lt, mid, rt;
cin >> n;
for(int i=0; i<n; i++) {
int temp;
cin >> temp;
V.push_back(temp);
}
cin >> want_to_find;
sort(V.begin(), V.end());
lt = 0;
rt = n-1;
while(lt <= rt) {
mid = (lt+rt) / 2;
if(V[mid] == want_to_find) {
cout << mid;
return 0;
}
else if(V[mid] > want_to_find) rt = mid - 1;
else if(V[mid] < want_to_find) lt = mid + 1;
}
return 0;
}
- V[mid] == want_to_find : 찾고자 하는 원소를 찾았을 때이다.
- V[mid] > want_to_find : 찾고자 하는 원소가 더 작을 때, 따라서 rt = mid -1;
- V[mid] < want_to_find : 찾고자 하는 원소가 더 클 때, 따라서 lt = mid + 1;
ex)
5
13 5 11 7 23
23
Author And Source
이 문제에 관하여(이분 검색(binary search) in C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@juwon9733/이분-검색binary-search-in-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)