알고리즘 - 탐색(선형, 이진, 점프, 보간, 삼진 탐색)

 

우리는 데이터를 많은 자료구조에 저장할 수 있다. 데이터를 저장하는 이유는 필요할 때 찾아서 연산하고 그 결과를 재사용하는 등 여러 추가 작업을 위한 것이다.

그러한 저장된 데이터를 찾아내기 위해 탐색 알고리즘에 대해 알아보자.

 

 

1. 순차 탐색(Sequential Search)

 

한글 명칭이 정확한지는 모르겠다. 이 방법은 배열이나 리스트 형태의 자료구조에서 순차적으로 앞 또는 뒤에서부터 모든 데이터를 탐색하는 방식이다.

순차 탐색의 예시로는 선형 탐색(Linear Search) 방식이 있다. 말 그대로 반복문을 사용해서 처음부터 끝까지 탐색을 수행하는 방식이다. 코드를 보면 바로 이해할 수 있다.

 

package com.test;

public class LinearSearch {
    public static void main(String[] args){
        int[] arr = new int[10];
        for(int i=0; i < arr.length; i++){
            // 1부터 20 까지의 난수 발생
            arr[i] = (int)(Math.random() * 20) + 1;
        }
        System.out.println();
        int x = 15;
        int result = search(arr, x);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

        x = 20;
        result = search(arr, x);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

        x = 10;
        result = search(arr, x);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);
    }

    public static int search(int[] arr, int x){
        int leng = arr.length;
        for(int i=0; i < leng; i++){
            if(arr[i] == x){
                return i;
            }
        }
        return -1;
    }
}

 

위 코드는 배열 내 데이터 값을 찾고 해당 데이터가 없으면 -1을 반환하고 있으면 해당 Index 값을 반환한다.

모든 배열의 데이터를 탐색하므로 시간 복잡도는 O(n) 이라고 볼 수 있다.

 

 

2. 구간 탐색(Interval Search)

 

이는 말 그대로 데이터가 저장된 리스트 혹은 배열의 특정 구간만을 탐색할 수 있도록 조절하는 방식이다. 원하는 데이터를 찾는데 특정 구간만으로 100% 탐색 가능을 보장하려면 어떻게 해야 할까?

답은 간단하다. 정렬된 상태의 데이터여야 한다. 구간 탐색 알고리즘들은 정렬된 상태의 데이터를 기준으로 탐색을 수행한다.

구간 탐색 알고리즘의 예시는 이진 탐색(Binary Search), 점프(?) 탐색(Jump Search), 보간 탐색(Interpolation Search), 지수 탐색(Exponential Search), 삼진(?) 탐색(Ternary Search) 등이 있다. 한국어 명칭이 정확한지는 모르겠다.

 

 

① 이진 탐색

 

이 방식은 반복적으로 전체 데이터가 저장된 구간을 반으로 나누어 데이터가 저장된 위치를 찾아가는 방식이다. 예를 들어 1, 2, 3, .. , 10의 데이터가 순서대로 배열에 저장되었다고 생각하자.

이 때, 3을 찾기 위해서 전체 구간의 최고 Index 값이 9일 것이므로 2로 나누어 index=4의 위치를 탐색한다. 4의 위치는 5일 것이며 찾고자 하는 값인 3은 5보다 작으니 0~4 Index 구간만 찾는다. 이 방식을 반복한다.

지속적으로 반으로 나누면서 탐색을 수행하므로 시간복잡도는 O(logn)이 된다.

코드는 다음과 같다.

 

package com.test;

public class BinarySearch {
    public static void main(String[] args){
        int[] arr = {-22, -15, 1, 7, 20, 35, 55};
        
        int x = -15;
        int result = iterativSearch(arr, x);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

        x = 20;
        result = recursiveSearch(arr, 0, arr.length-1, x);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

    }

    // 반복문을 이용한 방식
    public static int iterativSearch(int[] arr, int x){
        int start = 0;
        int end = arr.length-1;

        // 현재 탐색한 위치가 찾고자 하는 값보다 크냐 작냐에 따라 중간 index 계산을 위한 start / end 값을 변경함
        while(start <= end){
            int mid = (start + end) / 2;
            if(arr[mid] == x){
                return mid;
            } else if(arr[mid] < x){
                start = mid + 1;
            } else {
                end = mid-1;
            }
        }
        return -1;
    }

    // 재귀를 이용한 방식
    public static int recursiveSearch(int[] arr, int start, int end, int x){
        if(start > end) return -1;
        int mid = (start + end) / 2;

        if(arr[mid] == x) return mid;
        else if(arr[mid] < x) return recursiveSearch(arr, mid+1, end, x);
        else return recursiveSearch(arr, start, mid-1, x);
    }
}

 

 

 

② 점프 탐색(Jump Search)

 

이 방식 또한 정렬된 데이터를 탐색한다. 기본적으로 선형 탐색보다 탐색 수준을 줄여보겠다는 것에서 출발한다.

이 탐색은 Jump를 수행할 size를 지정해서 진행한다. 해당 값을 m이라고 가정 시, arr[m], arr[2m], ... , arr[nm] 과 같이 진행을 하는데 그 과정에서 현재 데이터와 찾고자 하는 데이터의 크기를 비교하여 Jump 구간 사이의 데이터가 찾고자 하는 데이터의 범위로 지정되도록 수행한다.

해당 범위로 지정된 구간을 다시 Jump 값을 재 지정하여 탐색하거나 선형 탐색을 진행하여 데이터를 찾는다.

그렇다면 Jump를 수행할 size는 어떻게 정할까? m이 그 크기라고 한다면 최악의 경우 n/m 만큼 탐색이 수행된다.

Jump를 통해 마지막까지 도달했는데 그것보다 1개 이전의 데이터가 찾는 데이터라면 점프 탐색 후 구간 내 선형 탐색을 진행한다는 가정 시에 탐색 횟수는 n/m + (m-1)이 된다.

즉, 최악의 경우가 위에 해당하는데 이 값은 √n 보다 작으므로 적절한 m = √n 이 된다. 시간 복잡도도 O(√n) 이다.

코드는 다음과 같다.

 

package com.test;

public class JumpSearch {
    public static void main(String[] args){
        int[] arr = {-22, -15, 1, 7, 20, 35, 55};

        int x = -15;
        int result = search(arr, x);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

        x = 20;
        result = search(arr, x);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

    }

    public static int search(int[] arr, int x){
        int leng = arr.length;

        // 점프 사이즈 지정
        int jump = (int)Math.floor(Math.sqrt(leng));

        // prev_idx는 이전 jump 위치의 index를 의미, 현재와 이전의 사이가 바로 찾고자 하는 데이터가 있는 구간임
        int prev_idx = 0;

        // 전체 배열 길이와 jump 위치 중 더 작은 값을 우선하여 현재 탐색 위치 지정
        int curr_idx = Math.min(jump, leng)-1;
        while(arr[curr_idx] < x){
            prev_idx = curr_idx;
            curr_idx += jump;
            if(prev_idx >= leng){
                return -1;
            }
        }

        // 구간 내 선형 탐색 수행
        while(prev_idx <= curr_idx){
            if(arr[prev_idx] == x){
                return prev_idx;
            }
            prev_idx++;
        }
        return -1;
    }
}

 

 

③ 보간 탐색(Interpolation Search)

 

이는 위의 이진 탐색(Binary Search)와 유사하지만 좀 더 보완한 방식이다. 이진 탐색은 항상 처음과 끝의 중간을 찾아 구간을 나누었다면 보간 탐색은 탐색할 위치를 계산하는 방법이 조금 복잡하다.

※ 계산법
pos = low + ((X - arr[low]) * (high - low)) / (arr[high] - arr[low])

* low : 현재 구간의 시작 Index
* high : 현재 구간의 마지막 Index
* X : 찾고자 하는 Data

 

위의 박스 부분과 같이 계산을 한다. 여기서 눈여겨 볼 점은, (X - arr[low]) 와 (arr[high] - arr[low]) 부분이다. 즉, 현재 구간 내 최대 최소값의 차이로 데이터 값 크기의 차이를 나누어 주고 있다. 

만약, 1~100 까지 숫자 50개가 랜덤하게 저장되었는데, 찾고자 하는 데이터가 크면 클수록 전체 분자의 크기가 높아져 탐색할 위치가 오른쪽으로 치우치게 된다. 작을 수록 왼쪽으로 치우치게 된다.

여기서 알 수 있는 사실이 있다. 이 데이터의 차이와 전체 구간의 길이가 영향을 미치기 때문에 전체 데이터 범위에서 균등하게 데이터가 분포되어 있을 수록 탐색하고자 하는 위치를 더 빠르게 찾을 수 있게 된다.

왜냐하면, 균등한 분포일수록 탐색하고자 하는 값과 배열 내 최소값의 차이로 해당 값의 분포상 위치를 더 정확하게 알아내기 쉬워지기 때문이다.

실제로 균등한 데이터 분포 일 때, 보간 탐색의 평균 시간 복잡도는 O(log(log(n)) 수준이다. 그러나, 최악의 경우에는 O(n) 수준이 될 수 있다.

자바로 구현한 코드는 다음과 같다.

 

package com.test;

public class InterpolationSearch {
    public static void main(String[] args){
        int[] arr = {10, 11, 13, 15, 17, 19, 20, 25, 26, 28, 30, 32, 35, 36, 40, 41, 42};

        int x = 40;
        int result = search(arr, x, 0, arr.length-1);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

        x = 11;
        result = search(arr, x, 0, arr.length-1);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

    }

    public static int search(int[] arr, int x, int low, int high){
        // 현재 범위 바깥에 있거나, low 값이 high를 넘겼다면 없는 것
        if(low > high || x < arr[low] || x > arr[high]) return -1;

        int pos = low + ((high - low) * (x - arr[low])) / (arr[high] - arr[low]);
        if(arr[pos] == x){
            return pos;
        }

        if(arr[pos] < x){
            return search(arr, x, pos+1, high);
        }

        if(arr[pos] > x){
            return search(arr, x, low, pos-1);
        }
        return -1;
    }
}

 

 

④ 지수 탐색(Exponential Search)

 

이것도 크게 다를 건은 없는데, 찾는 방식은 1, 2, 4, 8 .. 이렇게 Index 값을 지수 형태로 높여가며 구간을 탐색하는 방식이다. 다른 탐색과 마찬가지로, 이렇게 찾다가 해당되는 범위를 찾으면 그 안에서 다시 선형 혹은 이진 탐색을 수행해 값을 찾아낸다.

코드는 다음과 같다. 시간 복잡도는 O(logn) 이다.

 

package com.test;
import java.util.Arrays;

public class ExponentialSearch {
    public static void main(String[] args){
        int[] arr = {10, 11, 13, 15, 17, 19, 20, 25, 26, 28, 30, 32, 35, 36, 40, 41, 42};

        int x = 40;
        int result = search(arr, x);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

        x = 11;
        result = search(arr, x);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

    }

    public static int search(int[] arr, int x){

        // 가장 앞의 위치에 있다면 바로 반환, 1부터 시작할 것이기 때문
        if(arr[0] == x){
            return 0;
        }

        int i=1;
        // index 값이 배열 크기보다 작아야 그 안에서 구간을 찾는다.
        // 또한 배열의 값이 더 작은 동안에만 수행하여 구간을 찾는다.
        while(i < arr.length && arr[i] <= x){
            i = i * 2;
        }

        // 찾아낸 구간에서 이진 탐색으로 수행
        // i값이 전체 배열의 범위를 넘어갈 수 있으니 Math.min으로 설정
        return Arrays.binarySearch(arr, i/2, Math.min(i, arr.length-1), x);
    }
}

 

 

 

⑤ 삼진 탐색(Ternary Search)

 

이는 이진 탐색과 동일한데, 이진 탐색은 중앙을 기준으로 좌 / 우로 구간을 나누었다면 삼진은 좌, 중간, 우로 3개로 나누는 방식이다.

mid1 을 좌측 중간값, mid2를 우측 중간값이라고 한다면 다음과 같이 계산한다.

mid1 = low + (high - low) / 3
mid2 = right - (high - low) / 3

 

오, 그렇다면 동일한 O(logn) 의 시간복잡도가 예상되어도 밑의 값이 삼진은 3이고 이진은 2이므로 더 효과적이지 않을까?

그런데, 실제로는 이진 탐색이 더 선호된다. 왜냐하면, 최악의 경우에는 삼진 탐색 방식이 비교를 더 많이 해야 하기 때문이다. 그 내용은 이 링크를 참조 하면 될 것 같다.

 

코드는 다음과 같다.

package com.test;

public class TernarySearch {
    public static void main(String[] args){
        int[] arr = {-22, -15, 1, 7, 20, 35, 55};

        int x = -15;
        int result = recursiveSearch(arr, x, 0, arr.length-1);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

        x = 20;
        result = recursiveSearch(arr, x, 0, arr.length-1);
        System.out.println(result == -1 ? x + " does not exist" : "Found! Index is : " + result);

    }

    // 재귀를 이용한 방식
    public static int recursiveSearch(int[] arr, int x, int start, int end){
        if(start > end) return -1;
        int mid1 = start + (end - start) / 3;
        int mid2 = end - (end - start) / 3;

        if(arr[mid1] == x){
            return mid1;
        }

        if(arr[mid2] == x){
            return mid2;
        }

        if(x < arr[mid1]){
            return recursiveSearch(arr, x, 0, mid1-1);
        } else if(x > arr[mid2]){
            return recursiveSearch(arr, x, mid2+1, end);
        } else {
            return recursiveSearch(arr, x, mid1+1, mid2-1);
        }
    }
}

 

 

기타 다른 탐색 방식은 아래의 페이지에서 확인할 수 있다.

 

읽어주셔서 감사합니다.