[Java] 이진탐색(Binary Search)

이진탐색(Binary Search)를 하기 위해서는 배열이 정렬되어 있어야한다.

 

이진탐색은 배열을 계속해서 반으로 쪼개나아가면서 탐색하는 알고리즘이다.

배열 예시

위와 같은 배열이 있을 때 '43'원소의 index를 찾고자 하는 경우

 

배열의 양 끝의 index를 left와 right로 두고 반복문을 시작한다.

이 경우 mid의 index는 (left + right) / 2 가 된다.

mid에 해당하는 원소가 '43'이 아니므로 left를 (mid + 1)로 할당함으로써 기존 mid index를 포함한 왼쪽은 탐색하지 않는다.

그럼 위와 같이 left와 mid가 새롭게 할당된다.

새로운 mid에 해당하는 원소도 43이 아니므로 mid를 포함한 오른쪽은 탐색에서 제외하고 right를 (mid - 1)로 다시 할당해 준다.

그럼 위와 같이 right와 mid가 새롭게 할당된다.

여기서 mid는 (6 + 5) / 2 = 5이므로 mid는 5가 되고 arr[5]는 43이 아니므로 left를 (mid + 1)로 할당해준다.

그럼 위와 같이 되고 '43'의 index는 6이라는 것을 알 수 있게 된다.

 

위 과정을 코드로 구현하면 다음과 같다.

public class Main {
    public int solution(int M, int[] input) {
        int answer = 0;
        Arrays.sort(input);
        int leftIdx = 0, rightIdx = input.length - 1;

        while (leftIdx <= rightIdx) {
            int midIdx = (leftIdx + rightIdx) / 2;
            if (input[midIdx] == M) {
                answer = midIdx + 1;
                break;
            } else if (input[midIdx] > M) {
                rightIdx = midIdx - 1;
            } else {
                leftIdx = midIdx + 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[] input = new int[N];
        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }
        System.out.println(T.solution(M, input));
    }
}

결과

결과