[자료구조] 배열을 이용한 탐색

맵 구현 방법

1. 정렬되지 않은 배열을 이용하는 방법
2. 정렬된 배열을 이용하는 방법
3. 이진 탐색 트리를 이용하는 방법
4. 해싱을 이용하는 방법

정렬되지 않은 배열을 이용하는 방법

• 순차탐색(Sequential Search)
  • 가장 간단하고 직접적인 탐색 방법
  • 배열의 요소들을 처음부터 마지막까지 하나씩 검사하여 원하는 레코드를 찾는 방법

//c++
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;
}

정렬된 배열을 이용하는 방법

• 순차탐색
• 이진탐색
• 색인 순차 탐색
• 보간 탐색

순차탐색

• 정렬되지 않은 배열과는 달리, 배열 전체를 검색하지 않고도 탐색 항목의 존재 유무를 알 수 있음.
  

//c++
int sortedSequentialSearch(int list[], int key, int low, int high){
  if (key<list[low] || key>list[high])
  	return -1;
  for(int i=low; i<=high; i++){
  	if(low[i]==key) return i;
  	if(list[i]>key) return -1; // 정렬되지 않은 배열과의 차이점
   }
}

이진탐색(Binary Search)

• 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 부분배열에 있는지 오른쪽 부분배열에 있는지 판단하고 다음 단계의 탐색 범위를 반으로 줄임.
• 반드시 배열이 정렬되어있어야만 사용 가능
• 데이터의 삽입이나 삭제가 빈번한 경우에는 적합하지 않음.
  • 삽입/삭제 시 마다 배열을 정렬해주어야 하기 때문!!

//재귀(순환) 호출을 사용하는 이진 탐색 c++
int binarySearch(int list[], int key, int low, int high){
  if(low > high) return -1;
  int mid = (low + high) / 2;
  if(key == list[mid])
  	return mid; // 탐색 성공
  else if(key < list[mid])
  	return binarySearch(list, key, low, mid-1); // 왼쪽 부분리스트 탐색
  else
  	return binarySerach(list, key, mid+1, high); // 오른쪽 부분리스트탐색
}

//반복문을 이용한 이진탐색 함수 c++
int binarySearch(int list[], int key, int low, int high){
  int mid;
  while(low<=high){
    mid = (low + high) / 2;
    if(key == list[mid]) return mid;
    else if(key < list[mid]) high = mid-1;
    else low = mid+1;
  }
  return -1;
}

색인 순차 탐색

• 색인 순차 탐색(indexed sequential search) 방법은 인덱스(index)라 불리는 테이블을 사용하여 효율을 높이는 방법
• 인덱스 테이블에서 index[i] <= key < index[i+1]을 만족하는 항목을 찾아서 해당 범위의 항목들에 대해서만 검색
• 파일 처리, 데이터베이스 등의 응용 분야에서 많이 사용하는 방법

#include <iostream>
#define LIST_SIZE 9
#define INDEX_SIZE 3

using namespace std;

struct Index{
  int key; //키 값
  int index;//키값의 인덱스
}

int indexedSearch(int *list, int list_size, Index *index, int index_size, int key){
  if(key<list[0] || key>list[list_size-1]) return -1;
  
  for(int i=0; i<index_size-1; i++){
    if (index[i].key <= key && key < index[i+1].key)
      return sequentialSearch(list, key, index[i].index, index[i+1].index);
  }
  
  return sequentialSerach(list, key, index{i+1].index, list_size);
}

int main(){
  int list[LIST_SIZE] = {3, 9, 15, 22, 31, 55, 67, 88, 91};
  Index index[INDEX_SIZE] = {{3, 0}, {15, 2}, {67, 6}};//인덱스

  int num;
  cin >> num;

  int res = indexedSearch(list, LIST_SIZE, index, INDEX_SIZE, num);
  
  if(res >= 0) cout << "성공!!" << res << " 에 있습니다" << endl;
  else cout << "실패!!"<< endl;
  
  return 0;
}

보간탐색

• 보간탐색(interpolation search)은 사전이나 전화번호부를 탐색하는 방법과 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법
• 사전을 찾을 때 'z'로 시작하는 단어는 사전의 뒷부분에서 찾고, 'a'로 시작하는 단어는 앞부분에서 찾는 것고 같은 원리
• 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색
• 탐색위치 = ((key - list[low])/list[high]-list[low]) * (high-low) + low

int interpolationSearch(int list[], int list_size, int key){
  int low = 0;
  int high = list_size-1;

  while(list[low]<key  && key <= list[high]){
    int j = (int)((float)((key-list[low])/(list[high]-list[low]) * (high-low)) + low;
    
    if(key>list[j]) low = j+1;
    else if(key < list[j]) high = j-1;
    else return j;
  }
  return -1;
}