검색 (선형검색, 이진검색)

1. 검색 알고리즘

출처 : Do it 자료구조와 함께배우는 알고리즘 입문

일단 이 포스트에서 다룰 것은 a의 배열 검색이다.

배열 검색은 다음과 같은 알고리즘을 사용한다.

(1) 선형 검색 (Linear Search) : 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다.

(2) 이진 검색 (Binary Search) : 일정한 규칙으로 늘어놓은 데이터 모음에서 아주 빠른 검색을 수행한다.

(3) 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다.

 

2. 선형 검색 ( ==순차검색 )

배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘이다.

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날때 까지 맨 앞부터 순서대로 요소를 검색한다. (기본적으로 n(배열길이) for문 돌면서 키 값 요소와 비교 하는 방법)

class LinearSearch1 {
    static int seqSearch(int[] a, int n, int key) {
        int i = 0;
        while (true) {
            if (i == n) return -1;
            if (a[i] == key) return i;
            i++;
        }
/*
        // 동일

        for (int j = 0; j < n; j++) {
            if (a[j] == key) return j;
        }
        return -1;
*/
    }
}

 

선형 검색 시간 복잡도 : O(N)

 

3. 이진 검색

이전 검색 알고리즘을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬(sort)되어 있다는 것이다. 

이진 검색은 선형 검색 보다 좀 더 빠르게 검색 할 수 있다.

이진 검색은 배열의 값들이 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

이 알고리즘은 two pointers 처럼 lt와 rt를 배열의 양쪽 끝의 index로 정한다.

그리고 (lt + rt) / 2 인 mid 값을 정하고 계속 범위를 줄여나가면서 값을 검색하는 방식이다.

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

int binarySearch(int n, int m, int[] arr) {
// m이 찾는 값, n이 arr의 길이
    int answer = 0;
    Arrays.sort(arr);
    int lt = 0;
    int rt = n - 1;
    int mid;
    while (lt <= rt) {
        mid = (lt + rt) / 2;
        if (arr[mid] == m) {
            answer = mid + 1;
            break;
        }
        if (arr[mid] > m) rt = mid - 1;
        if (arr[mid] < m) lt = mid + 1;
    }
    return answer;
}

이전 검색은 검색을 반복 할 때마다 검색의 범위가 절반이 된다. 

따라서 시간 복잡도는 O(logN)으로 준다.

 

4. 자바의 Arrays.binarySearch에 의한 이진 검색

 

자바는 배열에서 이진 검색을 하는 메소드를 표준 라이브러리로 제공한다.

 

    int binarySearch(int n, int m, int[] arr) {
        int answer = 0;
        Arrays.sort(arr);
        answer = Arrays.binarySearch(arr, m) + 1;
        return answer;
    }

자바 표준 Arrays.binarySearch() 메소드를 까보면 다음과 같이 구현이 되어 있다.

public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
}
    
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                 int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

코드에서 볼 수 있듯, 검색을 성공하면 (key found ) mid를 return 한다. 그 key에 대한 위치 index값을 반환하는 것이다.

반면 검색에 실패한 경우 -(lt + 1)를 반환한다.