검색 (Search)

 

데이터 집합에서 특정 항목을 찾는 데 사용되는 방법

 

• 선형 탐색 (Linear Search):  데이터를 처음부터 끝까지 순차적으로 검색하는 방법이며 시간 복잡도는 O(n)

출처 : https://res.cloudinary.com/practicaldev/image/fetch/s--KwlAZJVc--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://dev-to-uploads.s3.amazonaws.com/i/19k583f8kooery0sthod.png

public class LinearSearchTest {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // 찾은 경우 해당 인덱스 반환
            }
        }
        return -1; // 찾지 못한 경우 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 8, 1, 7, 5};
        int target = 7;
        int result = linearSearch(arr, target);
        if (result != -1) {
            System.out.println("찾는 값 " + target + "은 배열의 " + result + "번째에 있습니다.");
        } else {
            System.out.println("찾는 값 " + target + "을 찾지 못했습니다.");
        }
    }
}

 

• 이진 탐색 (Binary Search): 정렬된 데이터에서 중간 값을 기준으로 검색 범위를 반으로 줄여가며 찾는 방법으로 시간 복잡도는 O(log n)

출처 : https://articles.wesionary.team/implementing-binary-search-a-simple-guide-3aa89453e0d2

public class BinarySearchTest {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid; // 찾은 경우 해당 인덱스 반환
            }
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 찾지 못한 경우 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 7, 8};
        int target = 5;
        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("찾는 값 " + target + "은 배열의 " + result + "번째에 있습니다.");
        } else {
            System.out.println("찾는 값 " + target + "을 찾지 못했습니다.");
        }
    }
}

 

• 해시 탐색 (Hash Search): 해시 함수를 사용하여 데이터를 저장하고 검색하는 방법으로 데이터를 키-값 쌍으로 저장하고 키를 해시 함수에 적용하여 값으므로 해시 함수의 성능에 따라 검색 속도가 달라짐

출처 : https://www.researchgate.net/figure/An-example-of-hash-search_fig1_220781807

public class HashSearchTest {
    public static void main(String[] args) {
        HashMap<String, Integer> hashMap = new HashMap<>();

        // 데이터 추가
        hashMap.put("apple", 100);
        hashMap.put("banana", 200);
        hashMap.put("cherry", 300);

        // 데이터 검색
        String keyToSearch = "banana";
        if (hashMap.containsKey(keyToSearch)) {
            int value = hashMap.get(keyToSearch);
            System.out.println(keyToSearch + "의 값은 " + value + "입니다.");
        } else {
            System.out.println(keyToSearch + "을 찾지 못했습니다.");
        }
    }
}

 

• 이진 탐색 트리 (Binary Search Tree - BST): 노드가 왼쪽 자식보다 작고 오른쪽 자식보다 큰 이진 트리이며 데이터를 정렬된 상태로 저장하고 검색, 삽입, 삭제 작업을 빠르게 수행하고 시간 복잡도는 평균적으로 O(log n)이지만 최악의 경우에는 O(n)이 될 수 있음

출처 : https://dream-and-develop.tistory.com/146

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class BinarySearchTreeTest {
    TreeNode root;

    public TreeNode search(int val) {
        return search(root, val);
    }

    private TreeNode search(TreeNode node, int val) {
        if (node == null || node.val == val) {
            return node;
        }
        if (val < node.val) {
            return search(node.left, val);
        }
        return search(node.right, val);
    }

    public static void main(String[] args) {
        BinarySearchTreeTest bst = new BinarySearchTreeTest();
        bst.root = new TreeNode(5);
        bst.root.left = new TreeNode(3);
        bst.root.right = new TreeNode(8);
        bst.root.left.left = new TreeNode(1);
        bst.root.left.right = new TreeNode(4);

        int target = 4;
        TreeNode result = bst.search(target);
        if (result != null) {
            System.out.println("찾는 값 " + target + "을 찾았습니다.");
        } else {
            System.out.println("찾는 값 " + target + "을 찾지 못했습니다.");
        }
    }
}