[코테] 이진 탐색

탐색에 대해서 알아보자!

데이터 속에서 원하는 값을 찾는 대표적인 방법에는
순차 탐색(Sequential search)과 이진 탐색(Binary search)이라는 방식이 있다.
이 둘은 어떤 차이가 있을까? 그리고 이진 탐색은 왜 더 빠르다고 할까?
지금부터 함께 알아보자!

순차 탐색(Sequential search)이란?

순차 탐색은 말 그대로 데이터를 앞에서부터 하나씩 차례대로 확인해보는 방법이다.

리스트의 첫 번째 인덱스부터 시작해서,
찾고자 하는 값이 나올 때까지 계속 다음 값을 확인해나간다.

👉 즉, 모든 데이터를 순서대로 검사하는 방식이라고 할 수 있다!

✅ 시간 복잡도는?

• O(N)
  데이터가 100개 있다면, 최악의 경우 100번을 다 확인해야 한다.
  데이터가 많아질수록 시간이 오래 걸리게 된다.

---

이진 탐색(Binary search)이란?

이진 탐색은 정렬된 데이터에서만 사용할 수 있는 탐색 방법이다.
리스트가 오름차순으로 정렬되어 있다는 조건이 필요하기에 처음에 배열을 정렬 하고 탐색한다.

탐색 방식을 알아보자!

1. 리스트의 가운데 값을 확인해본다.
2. 찾고자 하는 값이 가운데 값보다 작은지, 큰지를 비교한다.
3. 작다면 👉 왼쪽 절반만 다시 탐색
   크다면 👉 오른쪽 절반만 다시 탐색
4. 이렇게 범위를 반씩 줄여가며 반복해서 값을 찾는 방식이다.

💡 상세하게 알아본다면..!

• 먼저 최소 인덱스(min) 는 0, 최대 인덱스(max)는 배열 크기 - 1 로 셋팅 한다.
• 중간 인덱스(mid)는 (min + max) / 2 값을 내림해서 정수값이 나오도록 구한다.
• 중간값 = 리스트[mid]

그리고 찾고자 하는 값과 중간값을 비교한다.

• 찾는 값 < 중간값 → 최대 인덱스 = mid - 1
• 찾는 값 > 중간값 → 최소 인덱스 = mid + 1
• 찾는 값 == 중간값 → 값을 찾게 된다!

이 과정을 찾을 때까지 반복하면 된다.

✅ 시간 복잡도는?

• O(log(N))
  데이터가 많아도 탐색 시간이 급격히 줄어든다!
  예를 들어 1024개의 데이터가 있으면, 최대 10번 안에 찾을 수 있다.

순차 탐색은 순차적으로 인덱스 0부터 찾는값이 나올때까지 찾는다.

이진 탐색은 데이터 오름차순으로 정렬후 가운데 값을 찾고자 하는 값과 비교하여 업/다운으로 찾는다.

작은 데이터에서는 순차 탐색도 충분히 괜찮지만,
데이터의 양이 많아질수록 이진 탐색이 훨씬 더 효율적이라 데이터가 많고 정렬이 가능하다면 이진 탐색을 사용할것 같다!

---

정수 찾기로 탐색 익숙해지기!

이제 순차탐색과 이진 탐색의 개념을 알아 봤으니 문제를 직접 풀어보자!

정수 찾기 문제를 풀어보자! (링크 클릭시 프로그래머스로 이동!)

정수 리스트 num_list와 찾으려는 정수 n이 주어질 때, num_list안에 n이 있으면 1을 없으면 0을 return하도록 solution 함수를 완성해주세요.

순차 탐색으로 구현해보면 아래와 같이 구현해볼 수 있다!

public class Main {

    public static void main(String[] args) {
        int[] num_list = new int[5];
        num_list[0] = 15;
        num_list[1] = 98;
        num_list[2] = 23;
        num_list[3] = 2;
        num_list[4] = 15;
        System.out.println("TEST :: " + solution(num_list, 20));
    }

    public static int solution(int[] num_list, int n) {
        for (int num : num_list) {
            if (num == n) {
                return 1;
            }
        }
        return 0;
    }
}

코드를 돌려보면 배열에 20이 없으니 0 이 정상적으로 나오는것을 볼 수 있다.

값은 정상적으로 나오지만 num_list 크기가 크다면 위에 순차 탐색은 이진 탐색으로 구현한 코드보다 오랜 시간이 소요 될 것이다.

이를 이진탐색으로 구현해보자!

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] num_list = new int[5];
        num_list[0] = 15;
        num_list[1] = 98;
        num_list[2] = 23;
        num_list[3] = 2;
        num_list[4] = 15;
        System.out.println("TEST :: " + solution(num_list, 20));
    }

    public static int solution(int[] num_list, int n) {
        if (num_list == null || num_list.length == 0) {
            return 0;
        }
        Arrays.sort(num_list);
        int low = 0;
        int high = num_list.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (num_list[mid] == n) {
                return 1;
            }
            if (num_list[mid] < n) {
                low = mid + 1;
            }
            if (num_list[mid] > n) {
                low = mid - 1;
            }
        }
        return 0;
    }
}

 

이진 탐색으로 구현하면 코드는 길어지지만 성능적으로는 좋은 코드이다.

추가적으로 해당 문제를 아래와 같이 풀어 볼 수도 있다.

public static int solution(int[] num_list, int n) {
    return IntStream.of(num_list).anyMatch(v -> v == n) ? 1 : 0;
}

코드는 매우 간결해지지만 IntStream.of(...).anyMatch(...)의 경우 내부적으로 순차 탐색을 수행하기에 배열의 크기가 크다면 이진 탐색에 비해 느리므로 배열의 크기가 작거나 코드의 간결함이 중요한 경우에 사용하면 된다.

이와 같이 코드별로 장단점이 있으므로 상황에 맞게 코드를 구현하면 된다.

끝..!