[알고리즘 공부 15]

1.수찾기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[100001];
int alen, num;

void binSearch(int key)
{
	int start = 0;
	int end = alen - 1;
	int mid = 0;

	while (end >= start)
	{
		mid = (start + end) / 2;
		if (arr[mid] == key)
		{
			cout << "1" << '\n';
			return ;
		}
		else if (arr[mid] > key)
		{
			end = mid -1;
		}
		else
		{
			start = mid + 1;
		}
	}
	cout << "0" << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> alen;
	for (int i = 0; i < alen; i++)
	{
		cin >> num;
		arr[i] = num;		
	}

	sort(arr, arr+alen);

	int blen;
	cin >> blen;
	for (int i = 0; i < blen; i++)
	{	
		cin >> num;
		binSearch(num);
	}
}

이진탐색을 통해 배열안에 입력받은 인자가 존재하는 탐색하는 문제이다 이진탐색은 정렬을 우선적으로 해줘야하므로 c++ 에서 제공하는 sort함수를 통해 정렬은 한후 이진탐색을 구현하여 문제를 해결한다 이진탐색은 O(logN)을 가지므로 시간초과를 하지않고 문제를 해결할수있다.
이진탐색은 반복을 통해 구현하였고 start와 end를 가지고 둘이 중앙값을 mid로 하여 mid가 key과 같은지 검사하고 아니라면 중앙값과 key값을 비교해 start,end값을 수정하여 다시 mid를 정한다