탐색 알고리즘

탐색 알고리즘이란 지정된 데이터들 중에 원하는 값을 찾는 알고리즘이다.

 

선형 탐색 알고리즘 (Linear Search Algorithm)

맨 앞이나 맨 뒤부터 순서대로 하나하나 원하는 값을 찾아보고, 원하는 값을 찾았을 때 탐색을 종료하는 탐색 방법이다.

4를 찾을 때 맨 왼쪽에 있는 1부터 시작해서 하나씩 탐색한다.

원하는 값이 리스트의 맨 마지막 원소거나, 없는 경우 n번의 탐색 과정을 거치므로 시간 복잡도는 O(N)이다.

int arr[9] = { 3,1,5,7,2,4,9,6,8 };
int arr_size = sizeof(arr) / sizeof(int);

int linearSearch(int target) {
    // 찾은 값의 index 반환, 없으면 -1 반환
    int result = -1;

    for (int i = 0; i < arr_size; i++) {
        if (arr[i] == target) {
            result = i;
            break;
        }
    }
    return result;
}

 

이진 탐색 알고리즘 (Binary Search Algorithm)

중간 지점을 기준으로 데이터를 반씩 나눠서 탐색하는 알고리즘이다. 데이터가 미리 오름차순이나 내림차순으로 정렬되어 있는 경우에만 사용할 수 있다.

 

탐색의 진행 과정은 다음과같다.

1. 가운데에 있는 요소를 먼저 탐색한다.
2. 조건 요소가 가운데 요소보다 작은지 큰지를 보고, 탐색 범위를 좁힌다.
3. 탐색 범위를 좁힌 후에 다시 한 번 가운데를 탐색하며 이 과정을 원하는 결과를 찾을 때까지 반복한다.

이진 탐색 방법은 확인하는 데이터의 개수가 횟수마다 절반씩 줄어들기 때문에 시간 복잡도는 O(logN)이다.

이 특성 때문에 탐색해야 하는 데이터의 개수나 값이 1000만 단위 이상인 경우에 자주 쓰인다.

// 구현 코드
int binarySearch(int start, int end, int target){
    if (end-start<=1) {
        if (target == arr[start])
            return start;
        return -1;
    }
    int result = -1;
    int mid = (int)((start + end) / 2);
    if (arr[mid] == target)
        result = mid;
    else if (arr[mid] > target)
        result = binarySearch(start, mid, target);
    else if (arr[mid] < target)
        result = binarySearch(mid + 1, end, target);

    return result;
}

 

 

해시 탐색 알고리즘 (Hash Search Algorithm)

해시 탐색은 해시 함수를 이용하여 인덱스를 지정하여 값과 인덱스를 미리 연결해두고, 요소를 탐색할 때 찾고자 하는 요소의 해시값을 이용해 데이터에 빠르게 접근하여 탐색하는 알고리즘이다.

 

해시 함수와 해시 테이블을 포함한 해시 탐색에 대한 더욱 자세한 설명은 아래 게시글에서 정리해두었다.

https://nueahx7674.tistory.com/43

Hashing과 Hash Table

 

 

출처

https://hini7.tistory.com/121

[c++] 알고리즘 개념공부 :: 탐색 (선형 탐색, 이진 탐색, 해시 탐색)

https://bba-dda.tistory.com/21

[알고리즘] 탐색 알고리즘 (선형, 이분, 해시, BST)

https://all-young.tistory.com/9