검색

선형 검색

알고리즘 1

class MainClass {
    static int seqSearch(int[] a, int n, int key) {
        int i = 0;
        
        while (true) {
            if (i == n)
                return -1;  // 검색 실패 (-1을 반환)
            if (a[i] == key)
                return i;   // 검색 성공 (인덱스를 반환)
            i++;
        }
    }
}

// a : 검색할 배열
// n : 배열의 크기
// key : 찾을 값

 

알고리즘 2

class MainClass {
    static int seqSearch(int[] a, int n, int key) {
        for (int i = 0; i < n; i++) {
            if (a[i] == key)
                return i;
        return -1;
    }
}

 

알고리즘 3

class MainClass {
    static int seqSearchSen(int[] a, int n, int key) {
        int i = 0;
        
        a[n] = key;
        
        while (true) {
            if (a[i] == key)
                break;
            i++;
        }
        return i == n ? -1 : i;
    }
}

◽  앞선 알고리즘과는 다르게 입력할 배열의 요소 숫자보다 하나 더 큰 수만큼 배열을 생성한다.

◽  배열의 마지막 인덱스에 찾고자 하는 값을 넣고, 배열을 끝까지 탐색한 후 i 값을 확인하여 탐색에 성공했는지 실패했는지를 구분짓는 "보초법"이라는 알고리즘이다.

◽  시간 복잡도는 O(n)이다.

 

이진 검색

✔️  요소가 오름차순 혹은 내림차순으로 정렬됐다는 가정하에 사용할 수 있는 알고리즘이다.

알고리즘 1

class MainClass {
    // 요솟수가 n인 배열 a에서 key와 같은 요소를 이진 검색
    static int binSearch(int[] a, int n, int key) {
        int pl = 0;                  // 검색 범위의 첫 인덱스
        int pr = n - 1;              // 검색 범위의 끝 인덱스
        
        do {
            int pc = (pl + pr) / 2;  // 중앙 요소의 인덱스
            if (a[pc] == key)
                return pc;           // 검색 성공
            else if (a[pc] < key)
                pl = pc + 1;         // 검색 범위를 뒤쪽 절반으로 좁힘
            else
                pr = pc - 1;         // 검색 범위를 앞쪽 절반으로 좁힘
        } while (pl <= pr);
        
        return -1;                   // 검색 실패
    }
}

◽  시간 복잡도는 O(logn)이다.

 

Arrays.binarySearch

✔️  java.util.Arrays 클래스에서 제공하는 메서드

Arrys.binarySearch(x, key);

◽  배열 x에서 키 값이 key인 요소를 검색

◽  검색 성공 시 인덱스를 반환한다.

◽  검색 실패 시 삽입 포인트를 x라고 할 때 - x - 1을 반환한다. 삽입 포인트는 검색하기 위해 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스이다.