풀이 전략

• 탐색하는데 시간복잡도를 log(n)을 요구하므로 이진탐색을 생각할 수 있다.
  1) 노트에 필기하면서 규칙성을 찾아보면, mid값 == v[mid] 일 경우에 mid를 출력한다.
  2) mid값과 v[mid] 의 값을 비교하면서 규칙성을 찾을 수 있다.
  • value < index 일 때
    : -15[0] -6[1] 1[2] 3[3] 7[4]
    mid는 2이고, v[2] = 1 이다. mid > v[2] 인 상황에서..
    어차피 mid를 mid-- 해봣자 원하는 결론을 도출할 수 없다.
    이미 현재 시점에서 찾을 수 없다는 것을 도출할 수 있어서
    => 이때는 mid를 증가해야한다.
  • value > index는 반대로 동작한다.

소스코드

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

int binarySearch(vector<int>&v)
{
	int result = -1;
	int start = 0;
	int end = v.size() - 1;

	while (start <= end)
	{
		int index = (start + end) / 2;

		if (v[index] == index)
			return index;

		if (v[index] < index)
			start = index + 1;
		else if(v[index] > index)
			end = index - 1;
	}
	
	return result;
}


int main() {

	int n;
	cin >> n;
	vector<int>v(n);

	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	cout << binarySearch(v);

	return 0;
}