[Algorithm] 이분 탐색

시간복잡도

이분탐색이란 정렬된 배열 또는 리스트에서 특정한 값을 효율적으로 찾아내는 알고리즘 방식으로 탐색 범위를 절반으로 줄여나가기 때문에 시간 복잡도는 O(logN)이다.

원리

1. 배열의 중간값을 찾는다.
2. 찾는 값과 중간값을 비교한다.
   • 찾는 값이 중간 값보다 작으면 범위를 왼쪽 절반으로만 범위를 좁힌다.
   • 찾는 값이 중간 값보다 크면 범위를 오른쪽 절반으로만 범위를 좁힌다.
3. 반복하여 값을 찾거나 범위가 비게 되면 종료한다.

조건

1. 배열 값이 오름차순으로 정렬되어있어야 한다.
2. 반환 값이 존재하지 않을 경우 예외처리(-1반환)를 해주어야 한다.

백준 1920 수 찾기

아래 코드는 백준 1920 문제의 정답 코드이다. 이부분에서는 이분 탐색을 사용하였다.

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        List<Integer> arr = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            int K = Integer.parseInt(st.nextToken());
            arr.add(K);
        }
        Collections.sort(arr);

        int J = Integer.parseInt(br.readLine());
        List<Integer> numList = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int j = 0; j < J; j++) {
            numList.add(Integer.parseInt(st.nextToken()));
        }

        for (int k = 0; k < numList.size(); k++) {
            int sol = solution(numList.get(k), arr);
            sb.append(sol).append("\n");
        }

        System.out.println(sb);
    }

    static int solution(int K, List<Integer> arr) {

        int low = 0;
        int high = arr.size() - 1;

        while(low <= high) {
            int mid = (low + high) / 2;

            if(arr.get(mid) == K) {
                return 1;
            } else if (arr.get(mid) > K) {
                high = mid -1;
            } else if (arr.get(mid) < K) {
                low = mid + 1;
            }
        }

        return 0;
    }
}

---

아래 코드가 이진 탐색을 활용하여 일치하는 숫자가 존재하는지 찾는 것이다.
우선 문제는 K 값이 arr 안에 존재할 경우 1을 반환하며 존재하지 않을 경우 0을 반환하는 코드이다.

우선, 가장 작은값 = 0
가장 큰 값 = 리스트의 크기 -1 이다.
-1을 해주는 이유는 배열은 0부터 시작하고 배열의 마지막 인덱스 값은 사이즈 -1이 마지막 인덱스를 나타내기 때문이다.

while문을 통해 마지막 인덱스를 가리키는 값이 첫번째 인덱스 값보다 작거나 같을때가지 while을 진행하는 것이다.

중간값은 첫번째 인덱스 0과 마지막 인덱스 값 / 2를 하여 중간 값을 구한다. 이후 만약 중간 인덱스 값이 찾는 K값과 같을 경우 정답(1리턴)을 반환하고 만약 중간 값이 찾는 값보다 크다면 중간값을 기준으로 큰 범위(오른쪽) 값들은 다 크기때문에 제외할 수 잇다. 그렇기에 마지막 인덱스를 중간값 -1 로 지정해주고 다시 while문을 탐색하는 것이다.

반대로 만약 중간인덱스 값이 찾는 K 값보다 작다면 중간 인덱스값 기준 작은값(왼쪽)은 다 작은 값이므로 찾을 필요 없기에 low를 중간값 +1로 지정해주고 다시 while을 탐색하는 것이다.

실제로 코드를 짜보면 머릿속으로 더 잘 그려지니 직접 해보는것을 추천한다.

    static int solution(int K, List<Integer> arr) {

        int low = 0;
        int high = arr.size() - 1;

        while(low <= high) {
            int mid = (low + high) / 2;

            if(arr.get(mid) == K) {
                return 1;
            } else if (arr.get(mid) > K) {
                high = mid -1;
            } else if (arr.get(mid) < K) {
                low = mid + 1;
            }
        }

        return 0;
    }