이분 검색(binary search) in C++

Purple·2021년 9월 11일
0

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

profile
안녕하세요.

0개의 댓글