[알고리즘 문제]이분검색

▷ 문제

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면

이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

* 입력

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.

두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

* 출력

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

▷ 입력 예시

8 32

23 87 65 12 57 32 99 81

▷ 출력 예시

3

▷ 풀이

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

  public class Main {	
      public int solution(int n, int key, int[] arr){
        int answer = 0;
        int low = 0, high = n-1;
        
        Arrays.sort(arr);

        while(low <= high){
          int mid = (low + high) / 2;
          if(key == arr[mid]){
            answer = mid;
            break;
          } else if(key < arr[mid]){
            high = mid-1;
          } else{
            low = mid+1;
          }
        }

        return answer+1;
      }

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

        kb.close();

        System.out.println(main.solution(n, m, arr));
      }
    }