이분검색

설명

임의의 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가 있는데 mid숫자를 구해야한다. 시간복잡도는 o(n)이다.
mid = (lt+rt)/2
미드값이 찾는 숫자와 일치하면 찾은 것이다.
찾지 못하면 미드값이 찾는 값보다 크면  미드값부터 큰값은 제외된다. 반대로 미드값이 찾는값보다 작으면 미드값부터 작은수는 제외된다.

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

public class Main {

  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) { // lt가 rt 보다 작거나 같을때 까지
      int mid = (lt + rt) / 2;
      if (arr[mid] == m) {
        answer = mid + 1;
        break;
      }
      if (arr[mid] > m) {
        rt = mid - 1;
      } else {
        lt = mid + 1;
      }
    }

    return answer;
  }

  public static void main(String[] args) {
    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));
  }

}