3. 이분탐색

순차 탐색

순차로 데이터를 탐색한다는 의미

가장 기본 탐색 방법 -> 구현도 간단

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

데이터의 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점이 특징이다.
최악의 경우 시간 복잡도 O(N)이다.

이진 탐색

반으로 쪼개가면서 탐색하기
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

데이터가 무작위일 때에는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다.

위치를 나타내는 변수 3개를 사용하는데 시작점, 끝점, 중간점

찾으려는 데이터와 중간점 데이터를 반복적으로 비교

시간 복잡도 O(logN)

재귀함수 구현 코드

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

int n, target;
vector<int> arr;

int binarySearch(vector<int>& arr, int target, int start, int end)
{
	if (start > end) return -1;
	int mid = (start + end) / 2;
	if (arr[mid] == target) return mid;
	else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
	else return binarySearch(arr, target, mid + 1, end);
}
int main()
{
	cin >> n >> target;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		arr.push_back(x);
	}
	int result = binarySearch(arr, target, 0, n - 1);
	if (result == -1)
		cout << "원소가 존재하지 않습니다." << "\n";
	else
		cout << result + 1 << "\n";

}

for문 이진탐색

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

int binarySearch(vector<int>& v, int target, int start, int end)
{
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (v[mid] == target) return mid;
		else if (v[mid] > target) end = mid - 1;
		else start = mid + 1;
	}
	return -1;
}
int main()
{
	int n, target;
	vector<int> v;
	cin >> n >> target;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		v.push_back(x);
	}
	int result = binarySearch(v, target, 0, n - 1);
	if (result == -1) {
		cout << "원소가 존재하지 않습니다." << '\n';
	}
	else {
		cout << result + 1 << '\n';
	}
}

이진 탐색은 코딩테스트에서 단골로 나오는 문제 -> 가급적 외우자!

탐색 범위가 큰 상황에서 탐색을 가정하는 문제
탐색 범위가 2000만을 넘어가면 이진 탐색으로 문제에 접근하자.