Searching Algorithm, Search Algorithm   탐색 알고리즘, 검색 알고리즘

(2018-02-22)

순차탐색, 순차검색

1. 탐색/검색 알고리즘 (Searching Algorithm)

  ㅇ 탐색문제 
     - 순서 리스트(ordered list) 또는 비순서화된 리스트에서,
       어떤 원소/대상의 존재 및 그 위치를 찾는 것

  ㅇ 탐색문제의 해 : 원소의 위치


2. 주요 종류

  ※ 보통, 자료구조 형태에 따라 구분됨

  ㅇ 순차 탐색(sequential search)/선형 탐색(linear search)  ☞ 순차검색 구현 예시
     
Input  : arr[1,2,...,n], int n, int key
Output : int location

int sequential_search (arr[], n, key) {
   location = 1;
   while ( location <= n )
      if ( arr[location] == key )
         return location;
      location++;
   if ( location > n )
      return NULL;
} 
- 비 정렬 순차 검색 : 원하는 키값이 나올때까지 수행 - 기 정렬 순차 검색 : 중도에 키값 보다 큰 키값이 나오면 수행 중지 ㅇ 이진 탐색 (binary search) - 기 정렬되어있는 순서 리스트에서 가능한 검색 방법
Input  : int n, array Data[1,...,n], key x
Output : int location (검색 실패시 0)

void binary_search (int n, array Data[], key x, int &location) {
   int low=1, high=n, mid ;
   location = 0 ;
   while (low <= high and location == 0) {
      mid = (low + high)/2 ;
      if (x == Data[mid])
         location = mid ;
      else if (x < Data[mid])
         high = mid - 1 ;
      else 
         low = mid + 1;
   }
}
. 중앙 위치로부터 탐색 범위를 반씩 줄이면서 자료를 찾는 방법 3. 탐색 관련 용어키(Key) : 다른 원소와 구별할 수 있는 요소 ㅇ 레코드(Record) : 1 이상의 요소들이 서로 관련지어 모여진 자료 집합


[알고리즘 종류] 1. 알고리즘 분류 2. 탐색 알고리즘 3. 정렬 알고리즘 4. 그래프 알고리즘 5. 해쉬 알고리즘 6. 해싱 탐색 7. 최대 최소 구하기 8. 유클리드 알고리즘

 
        최근수정     요약목록(시험중)     참고문헌