이분 탐색(Binary search) 기본 개념

1. 탐색 종류

• 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진 탐색(이분 탐색) : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 (시작점, 끝점, 중간점을 이용하여 탐색 범위 설정)

2.이진 탐색의 시간 복잡도

한 단계마다 탐색 범위를 1/2로 줄이므로 연산 횟수는 log2(N)에 비례합니다.

• -> 시간 복잡도 O(logN)을 보장합니다.

3. 이진 탐색 소스코드 (반복문)

#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 (target > v[mid]) {
			start = mid + 1;
		}
		else if(target < v[mid]) {
			end = mid - 1;
		}
		else {
			return mid;
		}
	}
	return -1;
}


int n, target;
vector<int> v;
int main() {
	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';
	}


	return 0;
}

1. return -1 v에 찾는 원소가 없으면 -1 리턴
2. vector<int>&v &를 하지 않으면 값을 복사하기 때문에 O(N)의 시간복잡도가 생성되므로 레퍼런스 값을 매개변수로 지정해야합니다.
3. int result = binarySearch(v, target, 0, n - 1);
   함수는 인자를 4개 가져야한다 (벡터, 찾는 값, 시작점, 끝점)
4. 이진 탐색을 하기 전에 정렬을 해줘야 함!!!!!!