[알고리즘] 06.정렬, 이분검색과 결정알고리즘 / 08. 이분 검색(Binary Search) 이분 탐색

이분 검색(Binary Search)

설명

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

입력

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

출력

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

예시 입력 1

8 32
23 87 65 12 57 32 99 81

예시 출력 1

3

느낀점

lt, rt 의 포인트를 잘이용하면 쉽게 풀릴 수 있는 문제

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] arr = new int[n];

		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		System.out.println(T.solution(n, m, arr));
	}

	/*
	8 32
	23 87 65 12 57 32 99 81
	*/
	public int solution(int n, int m, int[] arr) {

		int answer = 0;

		Arrays.sort(arr);
		int lt = 0;
		int rt = n-1;

		while(lt <= rt) {
			int mid = (lt+rt)/2;

			//중간에 위치했을 때
			if(arr[mid] == m) {
				answer = mid+1;
				break;
			}

			//구하는 숫자가 중간보다 큰 수 일 때
			if(arr[mid] < m) {
				lt = mid;
			}
			//중간보다 작은 수 일 때
			else {
				rt = mid;
			}
		}
		return answer;
	}
}