[자료구조] 탐색(search)

탐색이란?

여러개의 가죠 중에서 원하는 자료를 찾는 작업

 

-탐색을 효율적으로 수행하는 것은 매우 중요

 

-탐색키(search key)

• 항목과 항목을 구별해주는 키(key)

-탐색을 위하여 사용되는 자료구조

• 배열, 연결리스트, 트리, 그래프 등

 

순차탐색

-탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법 :

   정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사

-평균 비교 횟수

  탐색 성공 : (n+1)/2번 비교

  탐색 실패 : n번 비교

 

-구현

int sequentialSearch(int list[], int key, int low, int high) {
    for (int i = low; i <= high; i++)
        if (list[i] == key)
            return i;
    return -1;
}

• 시간복잡도 : O(n)

 

이진탐색(Binary search)

-정렬된 배열의 탐색에 적합

• 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄여가며 탐색 진행

-구현

int binarySearch(int low, int high, int key) {
    while (low <= high) {
        int mid = (high + low) / 2;
        if (nums[mid] == key)  return mid;
        else if (nums[mid] < key)  low = mid + 1;
        else if (nums[mid] > key)  high = mid - 1;
    }
    return -1;
}

• 시간복잡도 : O(logn)

-이진 탐색과 이진 탐색 트리의 차이점

• 근본적으로 같은 원리에 의한 탐색 구조
• 이진 탐색은 자료들이 배열에 저장되어 있어 삽입/삭제가 매우 비효율 ->원소들을 모두 이동시켜야 함.
• 이진 탐색 트리는 매우 빠르게 삽입/삭제 수행
• 삽입,삭제가 빈번히 이루어진다면 이진탐색트리가 유리

-이진탐색트리의 시간 복잡도

• 균형트리 : O(log(n))
• 불균형트리 : O(n),순차탐색과 동일

참고)

이진탐색트리의 정의
-탐색작업을 효율적으로 하기 위한 자료구조
-key(왼쪽서브트리)≤key(루트노드)≤key(오른쪽서브트리)
-이진탐색을 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있다.