[알고리즘] 검색 Search - 순차 검색, 이진 검색 (자바/Java)

목차

검색

자료에서 원하는 항목을 찾는 작업

종류

순차 검색

이진 검색

인덱싱

순차 검색

일렬로 되어 있는 자료를 순서대로 검색

장점: 배열, 연결 리스트 등에서 유용

단점: 자료의 크기가 큰 경우에 비효율적

정렬X

첫 번째 원소부터 마지막 원소까지 키 값이 같은 원소가 있는지 검색

동일한 원소를 찾으면 검색을 중지하고 그 인덱스를 반환

마지막 원소까지 키를 찾지 못하면 실패

시간 복잡도: O(n)

정렬O

첫 번째 원소부터 키 값보다 큰 원소가 나올 때까지 검색

동일한 원소를 찾으면 반환, 키 값보다 큰 원소가 나왔는데 찾지 못하면 검색 실패

시간 복잡도: O(n)

그러나 정렬되지 않았을 때보다 평균 비교 횟수가 절반으로 줄어든다.

---

이진 검색

자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 계속해서 검색을 진행

검색을 수행할 때마다 범위가 반으로 줄어들어 효율적인 알고리즘

시간 복잡도: O(log n)

조건: 자료가 정렬되어 있어야 함

과정

1. 자료의 중앙에 있는 원소 선택
2. key값과 중앙 원소 비교
3. key값이 더 작으면 중앙 원소의 왼쪽에서, key 값이 더 크면 중앙 원소의 오른쪽에서 검색 수행

코드

package search;

public class BinarySearch {
    static int[] arr = { 2, 6, 8, 13, 22, 30, 46 };

    public static void main(String[] args) {
        int successKey = 6;
        int failKey = 24;

        System.out.println(binarySearch(successKey));
        System.out.println(binarySearch(failKey));
    }

    static int binarySearch(int key) {
        // 성공하면 index를, 실패하면 -1을 반환
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) { // start가 end보다 커지면 검색 종료
            int mid = (start + end) / 2;
            if (key == arr[mid])
                return mid;
            else if (key < arr[mid]) {
                end = mid - 1; // mid의 왼쪽
            } else {
                start = mid + 1; // mid의 오른쪽
            }

        }
        return -1;
    }

}