검색

검색

검색이란 저장되어 있는 자료중에서 원하는 항목(탐색키)을 찾는 작업을 말합니다. 

검색의 종류

순차 검색

일렬로 되어 있는 자료를 순서대로 검색하는 방법입니다. Array나 연결 리스트 등 순차구조로 구현된 자료구조에서 유용하지만 데이터가 많은 경우 비효율적인 알고리즘입니다.

• 데이터가 정렬되어 있을 경우

순차검색에서 데이터가 정렬되어 있을 경우에는 일반적인 for문 방식과 같으므로 자세하게 설명하지 않겠습니다.

• 데이터가 정렬되어 있지 않을 경우

데이터가 오름차순으로 정렬된 경우 자료를 순차적으로 검색하면서 키값을 비교하는데 원소의 키 값이 검색 대상의 키 값보다 크면 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료하는 방법.

    public static void main(String[] args) {
        int[] arr = {2, 4, 7, 9, 11, 19, 23};
        
        
        for(int i=0; i<arr.length; i++) {
            if(arr[i] == 10) {
                System.out.println("찾았다!!");
                break;
            } else if(arr[i] > 10) {
                System.out.println("10 없음!!");
                break;
            }
        }
    }

이진 검색

이진검색은 자료의 가운데에 있는 항목의 키 값과 비교 후 다음 검색 위치를 결정합니다. 검색 범위를 반으로 줄여가기 때문에 순차 검색보다 효율적입니다. 다만 이진 검색은 자료가 정렬된 상태에서만 사용이 가능합니다. 

1. 자료의 중앙에 있는 원소를 선택
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교하는데 "목표값 < 중앙 원소의 값" 의 경우 왼쪽 반에 대해서, "목표값 > 중앙 원소의 값"의 경우에는 오른쪽 반에 대해서 이진 검색을 수행합니다.

 
public class 이진검색 {
    public static void main(String[] args) {
        int[] arr = {2, 4, 7, 9, 11, 19, 23};
        boolean searchResult = binarySearch(arr, 0, arr.length-1, 7);
        System.out.println(searchResult);
    }
    
    private static boolean binarySearch(int[] arr, int start, int end, int key) {
        int middle = (start+end) / 2;
        
        if(start == end) {
            return false;
        }
        
        if(key < arr[middle]) {
            return binarySearch(arr, start, middle-1, key);
        } else if(key > arr[middle]) {
            return binarySearch(arr, middle+1, end, key);
        } else {
            return true;
        }
    }
}
 

인덱스

데이터베이스에서 유래되었으며 인덱스 저장공간을 이용하여 테이블에 대한 동작 속도를 높여주는 자료 구조입니다.  인덱스는 키-필드만 갖고있기 때문에 저장공간을 적게 차지합니다.