42번 이분검색 알고리즘

이분검색 사용x 

#include<iostream>
#include<vector>
#include<string.h>
#include<string>
using namespace std;

int main()
{
	int i, j;
	int n;
	int p;
	int tmp = 0;
	cin >> n >> p;
	vector<int> arr(n);

	for (i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	for (i = 1; i < n; i++)
	{
		tmp = arr[i];
		for (j = i - 1; j >= 0; j--)
		{
			if (arr[j] > tmp)//arr[i]의 값이 이동할때마다 바뀌기 때문에 tmp에 저장해둔 값으로 비교
			{
				arr[j + 1] = arr[j];
			}
			else
			{
				break;
			}
		}
		arr[j + 1] = tmp;
	}
	for (int i = 0; i < n; i++)
	{
		if (arr[i] == p)
		{
			cout << i+1;
			break;
		}
	}
}

 

이분검색 알고리즘 사용

#include<iostream>
#include<vector>
using namespace std;

int main()
{


	int i, j;
	int n;
	int p;
	int tmp = 0;
	cin >> n >> p;
	vector<int> arr(n);

	


	for (i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	for (i = 1; i < n; i++)
	{
		tmp = arr[i];
		for (j = i - 1; j >= 0; j--)
		{
			if (arr[j] > tmp)//arr[i]의 값이 이동할때마다 바뀌기 때문에 tmp에 저장해둔 값으로 비교
			{
				arr[j + 1] = arr[j];
			}
			else
			{
				break;
			}
		}
		arr[j + 1] = tmp;
	}
	int fq=0;
	int bq=n-1;
	int mid;
	while (fq <= bq)
	{
		mid = (fq + bq) / 2;
		if (arr[mid] == p)
		{
			cout << mid + 1;
			break;
		}
		else if (arr[mid]>p)
		{
			bq = mid - 1;
		}
		else if (arr[mid] < p)
		{
			fq = mid + 1;
		}
	}

	

	
	
}

 

sort 함수 사용

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int mid;
	int fq;
	int bq;
	int p;
	int N;
	cin >> N >> p;
	vector<int> arr(N);

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	sort(arr.begin(), arr.end());

	fq = 0;
	bq = N - 1;
	while (fq <= bq)
	{
		mid = (fq + bq) / 2;
		if (arr[mid] == p)
		{
			cout << mid + 1;
			break;
		}
		else if (arr[mid] > p)
		{
			bq = mid - 1;
		}
		else if (arr[mid] < p)
		{
			fq = mid + 1;
		}
	}


}