[Java / 알고리즘] 탐색 알고리즘. 순차 탐색(선형 탐색), 이진 탐색

탐색이란 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 말한다.

 

 

1. 순차 탐색(Sequential Search), 선형 탐색(Linear Search)

순차 탐색 또는 선형 탐색이라고 한다.

데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법이다.

 

 

 

[ 코드 ]

public class main {
    public static void main(String[] args) {
        int[] array = {23, 45, 12, 67, 89, 34, 56, 72};
        int target = 34;

        // 선형 탐색을 수행하고 결과를 출력
        int result = linearSearch(array, target);
        if (result == -1) {
            System.out.println("Element " + target + " not found in the array.");
        } else {
            System.out.println("Element " + target + " found at index " + result + ".");
        }
    }

    // 선형 탐색 구현
    static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // 원소를 찾으면 인덱스 반환
            }
        }
        return -1; // 원소를 찾지 못한 경우 -1 반환
    }
}

 

 

시간 복잡도

최악의 경우 배열의 크기 n * n번 반복하므로 시간 복잡도는 O(n^2) 이다.

 

 

2.  이진 탐색(Binary Search)

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법이다.
• Divide - 리스트를 두 개의 서브 리스트로 나눈다.
• Conquer
  • 검색할 숫자 (target) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
  • 검색할 숫자 (target) < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

 

 

 

[ 코드 ]

public static void main(String[] args)
{
    int[] sortedArray = {1, 2, 4, 7, 9, 12, 15, 18, 22, 27};
    int target = 15;

    // 이진 탐색을 수행하고 결과를 출력
    int result = binarySearch(sortedArray, target);
    if (result == -1) {
        System.out.println("Element " + target + " not found in the array.");
    } else {
        System.out.println("Element " + target + " found at index " + result + ".");
    }
}

// 이진 탐색 구현
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;
        }
        // 중간값이 타겟보다 작으면 오른쪽 반만 확인
        else if(arr[mid] < target) {
            left = mid + 1; // 중간값은 볼필요 없으므로 +1
        }
        // 중간값이 타겟보다 크면 왼쪽 반만 확인
        else {
            right = mid - 1;
        }
    }
    // 타겟을 찾지 못한 경우
    return -1;
}

 

 

시간 복잡도

N개의 리스트를 매번 2로 나누어 1이 될 때까지 비교연산을 k회 진행하므로 시간 복잡도는 O(logn) 이다