이진 탐색 - 2. 고정점 찾기

문제

고정점(Fixed Point)이란, 수열의 원소 중에서 그 값이 인덱스와 동일한 원소를 의미합니다. 예를 들어 수열 a = [-15, -4, 2, 8, 13]이 있을 때 a[2] = 2, 고정점은 2가 됩니다.
하나의 수열이 N개의 서로 다른 원소를 포함하고 있으며, 모든 원소가 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 고정점이 있다면, 고정점을 출력하는 프로그램을 작성하세요. 고정점은 최대 1개만 존재합니다. 만약 고정점이 없다면 -1을 출력합니다.
단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간초과' 판정을 받습니다.

입력 조건

첫째 줄에 N이 입력됩니다. (1 <= N <= 1,000,000)
둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
(-10^9 <= 각 원소의 값 <= 10^9)
출력 조건

고정점을 출력한다. 고정점이 없다면 -1을 출력합니다.
입력 예시 1

5

-15 -6 1 3 7
출력 예시 1

3
입력 예시 2

7
-15 -4 2 8 9 13 15
출력 예시 2

2

입력 예시 3

7
-15 -4 3 8 9 13 15
출력 예시 3

-1

구현코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] num = new int[n];
		for(int i = 0 ; i < n ; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		int start = 0;
		int end = n -1;
		int mid = 0;
		boolean find = false;
		while(start <= end){
			mid = (start + end) / 2;
			if(num[mid] == mid ){
				find = true;
				break;
			}else if(num[mid] > mid){
				end = mid -1; 
			}else{
				start = mid + 1;
			}
			
		}
		if(find){
			System.out.println(mid);
		}else {
			System.out.println(-1);
		}
	}

}

코드해석

이진 탐색문제를 풀때는 값이 정렬되어있는지, 안되어있다면 정렬해도 상관이 없을지, 이진탐색을 진행 할 때 반복문의 탈출 조건은 어떻게 해야하는지를 생각해야하는거같다.

이문제는 모든 원소가 오름차순으로 정렬되어 있다고 되어있고 우리가 찾고자 하는 것은 위치와 값이 같은 것을
찾는 것이기 때문에 비교값을 같을때 ,클때 작을 때를 비교하여 같을때가 나오면 find 변수값을 true 로 바꿔준다.
그리고 반복문을 빠져나와서 만약 find 가 true 라면 mid 값을 출력하고 false 라면 -1을 출력한다.