Chapter 02. 탐색

 

2.1 선형 탐색

  2.1-1 탐색 알고리듬

    Def) 탐색 알고리듬(Search Algorithm)

      어떤 자료구조 안에 저장되어 있는 자료를 

      찾아오는 알고리듬.

 

    Note) 매우 다양한 알고리듬이 여기 포함됨.

      ex. 배열에서 제일 큰 값 찾기

          데이터 베이스에서 레코드 하나 읽어오기

          배낭(knapsack) 문제 등

 

    Note) 대표적인 탐색 알고리듬

      1. 선형 탐색

      2. 이진 탐색

      3. 해시 기반 탐색

 

  2.1-2 선형 탐색

    Def) 선형 탐색(Linear Search)

      자료구조의 모든 자료를 순서대로 훑어가며 

      원하는 자료를 찾는 알고리듬.

 

    Note) 기초문법 배열편에서 많이 해보았기 때문에,

      관련 예제는 생략함.

 

 

2.2 이진 탐색

  2.2-1 이진 탐색이란,

    Note) 업-다운 게임을 생각 해 보자.

      당연히 우리는 수의 범위중 중간을 가장 먼저 부름.

      왜? 절반씩 날리는게 가장 적은 횟수로 정답에 갈 수 있으니까.

      우리도 모르게 이진 탐색을 쓰고 있던 것.

 

    Note) 근데 여기엔 전제 조건이 있음.

      숫자가 모두 정렬되어 있어야 함.

      ex. 선생님 나이 맞추기로 업다운 게임 한다고 해보자.

        선생님 나이는 20~30살 사이라고 했는데, 

        20, 21, 22, 25, 23, 29, 30, ... 이렇게 뒤죽박죽이라면?

 

    Def) 이진 탐색(Binary Search)

      정렬되어 있는 자료구조에 절반씩 자료를 제거해가며

      원하는 자료를 찾는 알고리듬.

      한 단계가 진행 될 때마다, 탐색 범위가 절반씩 줄어들어서

      이진 탐색이라고 부름. 재귀함수로 쉽게 구현가능.

 

    Note) 즉, 이진 탐색은

      정렬되어 있는 자료구조에 특화되어 있다고 볼 수 잇음.

 

    Ex02020101) BinarySearch.c

/* main.cpp */

#include <iostream>
#include <vector>

using namespace std;

enum { 
    LENGTH = 1024,
    INVALID_INDEX = -1
};

size_t binarySearch(int nums[], size_t length, int k);

int main(void)
{
    int nums[LENGTH];

    for (size_t i = 0; i < LENGTH; ++i) {
        nums[i] = i * 2;
    }

    cout << binarySearch(nums, LENGTH, 512) << endl;
    cout << (int)binarySearch(nums, LENGTH, 511) << endl;

    return 0;
}

size_t binarySearch(int nums[], size_t length, int k)
{
    int left, mid, right;
    left = 0;
    right = length - 1;

    while (left <= right) {
        mid = (left + right) / 2;
        if (k < nums[mid]) {
            right = mid - 1;
        } else if (k == nums[mid]) {
            return mid;
        } else {
            left = mid + 1;
        }
    }

    return INVALID_INDEX;
}

 

2.3 해시 기반 탐색

  2.3-1 해시 기반 탐색

    Note) 우리가 병원에 갔다고 가정해 보자.

      어떻게 데스크 선생님들은 주민등록번호만 말해도

      순식간에 우리 정보를 찾아내실까?

      그냥 툭 치면 툭하고 나오는 수준.

      혹은 우리 뇌는 어떤 자료구조로 이뤄졌길래,

      특정 키워드(중학교 졸업식날)만 생각해도 그날의 기억이 

      순식간에 떠오르는 걸까?

 

    Def) 해시 기반 탐색

      키-벨류 쌍으로 데이터를 저장해서, 

      특정 키가 들어오면 그에 해당하는 벨류를 곧바로 반환하는 탐색 알고리듬.

      자세한 이야기는 이후에 배울 해시 테이블에서 보도록 하자.

 

 

2.4 요약

  2.4-1 선형 탐색 Vs. 해시 기반 탐색

선형 탐색	해시 기반 탐색
모든 데이터에 사용 가능	모든 데이터에 사용 가능
O(N)	O(1)
N만큼의 용량이 필요	N보다 큰 용량이 필요 (이후에 배움)

 

    Note) 속도와 용량 사이의 밸런스

      그런데, 용량은 같은데 O(N)보다 빠를 수 있다면?

      그런 알고리듬이 바로 이진 탐색.

 

  2.4-2 정렬 후 이진 탐색 Vs. 선형 탐색

배열이 안 바뀌는 경우	배열이 바뀌는 경우
탐색할 일이 많은 경우 정렬 한 번 후, 이진 탐색 x번 O(정렬) + O(logN) * x	요소를 삽입하는 경우만 문제
탐색을 한 번만 할 경우 선형 탐색 O(N)	보통 선형 탐색을 사용함.
	이진 탐색을 사용하려면? 탐색 전에 배열을 정렬해야 함. 이는 배열이 바뀔때마다 곧바로 배열이 바뀐적이 있다면 탐색 직전에
	이때문에 선형 탐색보다 느릴 수 있음. 탐색과 배열 변경 빈도에 따라 탐색 빈도가 높을수록 유리

 

    Ex02040201) SearchInRotatedArray.c

/* main.cpp */

#include <iostream>

using namespace std;

enum {
    LENGTH = 1024,
    INVALID_INDEX = -1
};

size_t binarySearch(int nums[], size_t start, size_t end, int k);
size_t indexOfRotatedArray(int nums[], int start, int end, int k);

int main(void)
{
    int nums1[LENGTH];
    for (size_t i = 0; i < LENGTH; ++i) {
        nums1[i] = i * 2; 
    }

    cout << binarySearch(nums1, 0, LENGTH - 1, 512) << endl;
    cout << (int)binarySearch(nums1, 0, LENGTH - 1, 511) << endl;

    int nums2[10] = {5, 6, 7, 8, 9, 0, 1, 2, 3, 4};

    cout << binarySearch(nums2, 0, 9, 7) << endl;
    // cout << (int)binarySearch(nums2, 0, 9, 3) << endl;

    cout << indexOfRotatedArray(nums2, 0, 9, 7) << endl;
    cout << (int)indexOfRotatedArray(nums2, 0, 9, 3) << endl;

    return 0;
}

size_t binarySearch(int nums[], size_t start, size_t end, int k)
{
    if (start > end) {
        return INVALID_INDEX;
    }

    size_t mid = (start + end) / 2;

    if (k == nums[mid]) {
        return mid;
    } else if (k < nums[mid]) {
        return binarySearch(nums, start, mid - 1, k);
    } else {
        return binarySearch(nums, mid + 1, end, k);
    }
}

size_t indexOfRotatedArray(int nums[], int start, int end, int k) {
    if (start > end) {
        return -1;
    }
    int mid = (start + end) / 2;
    if (nums[mid] == k) {
        return mid;
    }
    if (nums[start] <= nums[mid]) {
        if (nums[start] <= k && k <= nums[mid]) {
            return indexOfRotatedArray(nums, start, mid - 1, k);
        }
        return indexOfRotatedArray(nums, mid + 1, end, k);
    }
    if (nums[mid] <= k && k <= nums[end]) {
        return indexOfRotatedArray(nums, mid + 1, end, k);
    }
    return indexOfRotatedArray(nums, start, mid - 1, k);
}