이분 검색

문제

나의풀이

import java.util.*;
class Main {
	public int solution(int n,int m, int[ ]arr) {
		int answer = 0;
		Arrays.sort(arr);
		int lt = 0, rt = n-1;
        //lt가 rt를 넘어섰지만 찾는값이 없으면 while문이 종료된다.
		while(lt <= rt) {
			int mid = (lt+rt)/2;
			//mid번째 값과 m이 같을경우.
			if(arr[mid] == m) {
				answer = mid+1;
				break;
			}
			//mid번째 값이 m보다 큰 경우
			if(arr[mid] > m) rt = mid-1;
            //mid번째 값이 m보다 작은 경우
			else lt = mid+1;
		}
		return answer;
	}

		    
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = kb.nextInt();
		}
		System.out.println(T.solution(n,m, arr));
		
	}
	
}

풀이방법

lt는 0 rt는 배열의 끝 index로 지정해두고 시작한다.
mid는 배열의 중간지점 (lt+rt)/2.

만약 mid가 m(타겟넘버)보다 크다면, mid~rt부분은 전부 제외시켜도 되므로
rt= mid-1이 되고 다시 탐색을 시작한다.

만약, mid가 m(타겟넘버)보다 작다면, lt~mid부분은 전부 제외시켜도 되므로
lt = mid+1이 되고 다시 탐색을 시작한다.

만약 mid==m이라면, answer는 mid+1번째 위치에 있다.

핵심키워드

이분탐색을 활용하면 배열길이의 1/2만큼만 탐색을 해도 값을 구할수있다!