[Binary Search] 개념 + 7795번

이분탐색 ? 정렬이 보장되어있는 배열에서, 이분을 하면서 탐색하는기법

이분탐색은 전형적인 변수 세팅을 사용한다.

 

왼쪽, 오른쪽의 포인터 두개를 가지고 시작한다.

항상 가운데의 인덱스를 보고, 해당 인덱스와 , 타겟을 비교하고, 해당 비교를 통해 포인터 L 혹은 R을 비교하면서 포인터를 이동시킨다.

 

https://www.acmicpc.net/problem/7795

7795번: 먹을 것인가 먹힐 것인가

 

 

이분탐색에 대한 예제이다.

 

쉽게말하면, 한 집합을 정렬, 그리고 한집합을 하나씩 가져와서 값을 비교한다.

값이 만약에 크다면 left를 옮겨서 더 큰 index를 체크하고, 아니라면 right를 옮기면서, maxindex를 찾는다.

코테에서 탐색, 이분탐색에 대한 고민은 시간제한을 체크한다.

경우의 수가 1억 = 1초인것을 감안하여, 최대 경우의 수를 시간초과에 비교하면서 생각하고 풀어야 한다.