[Algorithm/Java] 알고리즘 자바 이진 탐색, 이분 검색 (코딩테스트, Sorting, Searching, 정렬, 검색, Binary Search, 이진 검색)

---

1. 문제 설명

• 설명
  임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.
• 입력
  첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
  두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
• 출력
  첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

 

 

2. 문제 코드 및 풀이 설명

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

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

  // 해결방법
  // 기본적인 이분검색 알고리즘
  // 배열을 정렬
  // 첫번째와 마지막에 인덱스 변수를 설정
  // 두 인덱스의 가운데 값을 검사하여 찾을 값과 같다면 가운데 값을 리턴
  // 가운데 값이 크다면 마지막 값을 가운데 값으로 작다면 첫번째 값을 가운데 값+1으로 바꿔준다
  // 값을 찾을 때까지 반복
  public int solution(int n, int m, int[] arr) {
    int answer = 0;
    int left = 0, right = n - 1; // 검색 배열의 가장 왼쪽과 오른쪽 위치 변수
    // 이분검색을 위한 배열 정렬
    Arrays.sort(arr);

    while (true) {
      int mid = (left + right) / 2;
      if (arr[mid] == m) { // 가운데 값과 같다면 즉 찾았다면 값을 리턴
        answer = mid + 1;
        break;
      } else if (arr[mid] > m) right = mid; // 크다면 오른쪽을 날림
      else left = mid + 1; // 작다면 왼쪽을 날림
    }
    return answer;
  }
}

 

3. 출력 예시

입력
8 32
23 87 65 12 57 32 99 81

출력
3

 

 

---

위의 내용은 인프런에서 수강할 수 있는 김태원님의 자바 알고리즘 문제풀이 강의를 바탕으로 공부한 내용을 정리한 내용입니다!

https://inf.run/iAi6

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의