[Algorithm] 순차 탐색과 이진 탐색

순차 탐색 (Sequential Search)

· N개의 데이터가 있을 때, 해당 데이터를 차례대로 하나씩 확인하여 처리하는 방법

· 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인

· 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요 -> 최악의 경우 시간 복잡도: O(N) 

 

▶ 예시 - 순차 탐색으로 특정 문자열의 위치 찾기

public class SequentialSerach {
    public static void main(String[] args){
        String[] strings = {"a","b","c","d","e"};
        String target = "d";
        for(int i=0; i< strings.length; i++)
            if(strings[i].equals(target))
                System.out.println("탐색 중인 인덱스 위치는 "+i+"입니다.");
    }
}

 

이진 탐색 (Binary Search)

· 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 

· 시간 복잡도 O(logN)

· 배열 내부 데이터가 정렬되어 있어야만 사용 가능 하지만, 빠르게 데이터 탐색 가능

 

이진 탐색 원리

· 위치를 나타내는 3개의 변수 시작점, 끝점, 중간점을 사용

· 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교

 

▶ 예시 -  이진 탐색으로 정렬된 10개의 데이터 중 원하는 데이터 찾기

 

1. 시작점과 끝점 사이에 중간점을 정한다. 중간점이 실수면 소수점 이하는 버린다. 중간점의 데이터 8이 찾으려는 데이터 4보다 더 크다.

   중간점 이후의 값은 확인할 필요가 없으므로 끝점을 [4]의 이전인 [3]으로 옮긴다.

2. 시작점은 [0], 끝점은[3], 중간점은 [1]이다. 중간점에 위치한 데이터 2는 찾으려는 데이터 4보다 작다.

    값이 2 이하인 데이터는 더 이상 확인할 필요가 없으므로 시작점을 [2]로 변경한다.

3. 시작점은 [2], 끝점은 [3], 중간점은 [2]다. 중간점에 위치한 데이터가 찾으려는 데이터이므로 탐색을 종료한다.

 

· 이진 탐색을 구현하는 방법은 두 가지: 재귀 함수, 반복문

public class BinarySerachRecursion {
    public static void main(String[] args){
        int[] arr = {0,2,4,6,8,10,12,14,16,18};
        int target = 4;
        BinarySerachRecursion binarySerach = new BinarySerachRecursion();
        int result = binarySerach.binarySearch(arr, target, 0, arr.length);

        if(result == -1) System.out.println("탐색하는 값이 존재하지 않습니다.");
        else System.out.println(target+"의 위치:"+result);

    }

    int binarySearch(int[] arr, int target, int start , int end){
        if(start>end) return -1;

        int mid = (start+end)/2;
        //찾은 경우 중간점 위치 반환
        if (arr[mid] == target) return mid;
        //중간점 값보다 찾는 값이 작은 경우 왼쪽 확인
        else if(arr[mid] > target) return binarySearch(arr,target,start,mid-1);
        //중간점 값보다 찾는 값이 큰 경우 오른쪽 확인
        else return binarySearch(arr,target,mid+1,end);
    }
}

 

public class BinarySerachIteration {
    public static void main(String[] args){
        int[] arr = {0,2,4,6,8,10,12,14,16,18};
        int target = 4;
        BinarySerachIteration binarySerach = new BinarySerachIteration();
        int result = binarySerach.binarySearch(arr, target, 0, arr.length);

        if(result == -1) System.out.println("탐색하는 값이 존재하지 않습니다.");
        else System.out.println(target+"의 위치:"+result);
    }

    int binarySearch(int[] arr, int target, int start ,int end){

        while (start<=end){
            int mid = (start+end)/2;
            if (target == arr[mid]) return mid;
            else if(target < arr[mid]) end = mid-1;
            else start = mid+1;
        }
        return -1;
    }
}