자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Sorting and Searching(정렬, 이분검색과 결정알고리즘)_이분검색)

 

8. 이분검색

 

예시 입력 1 

8 32
23 87 65 12 57 32 99 81

예시 출력 1

3

 

 

arr이라는 1차원 배열에 입력값들을 받았고, 받은 다음 Array.soft()를 통해 오름차순 정렬한 상황입니다.

정렬된 상황에서 m인 32가 어디있는가를 찾는 것입니다.

0번인덱스가 첫번째라 인덱스+1해서 32번은 2번째 인덱스이자, 3번째에 있다라고 할 수 있습니다.

 

이분검색은 무조건 정렬이 되어있어야 합니다. 오름차순이던 내림차순이던 정렬되어있는 상황에서만 통하는게 이분검색입니다.

앞에서부터 하나하나씩 보는건 순차검색입니다. 순차검색으로 제일 뒤에 있는 99를 찾으려면 O(n)시간복잡도가 걸립니다.

 

이분검색은맨 왼쪽을 가르키는 lt를 0으로 초기화, rt는 n-1로 시작합니다.

그리고 lt와 rt의 중간 지점을 가르키는게 mid = (lt + rt) / 2하면 됩니다.

그리고 arr[mid]가 m이라면 정답을 찾은거거고 아닐 경우 추가작업이 필요 합니다.

arr[mid]값이 m값보다 크면, 내가 찾고자 하는건 작은쪽에 있다는 것을 의미하니까 큰쪽은 보지 않아도 됩니다.

만약 내가 찾고자 하는게 81이라면 else분기로 들어갑니다. (첫번째 사진 : 작은쪽 /  두번째 사진 : 큰쪽)

 

 

그리고 이걸 계속 탐색하고 좁혀나가면 rt가 작아지고 lt가 커지면 멈춰야 합니다 (lt > rt)

이런 경우는 m값이 배열에 없는 값이 주어질 경우 입니다.

 

강의 풀이(Time: 299ms Memory: 32MB)

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, rt = n-1;
        // lt가 rt보다 커지면 멈추게 반복문 설정
        while (lt <= rt) {
            int mid = (lt+rt)/2;
            if(arr[mid]==m) {
                answer = mid+1; // mid는 인덱스 번호고 우리가 찾는건 번째
                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 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));
    }
}