탐색 (Search), 순차 탐색, 이진 탐색, 색인 순차 탐색, 보간 탐색

탐색이란

여러 개의 자료 중에서 원하는 자료를 찾는 작업
탐색키와 데이터로 이루어진 여러개의 항목 중에서 원하는 탐색 키를 가지고 있는 항목을 찾는 방법

정렬되지 않은 배열에서의 탐색

1. 순차 탐색 (Sequential Search)

데이터의 첫 부분부터 순차적으로 데이터를 비교하여 원하는 데이터의 위치를 찾는 알고리즘
탐색 방법중에서 가장 간단하고 직접적인 탐색 방법

 

https://velog.io/@limsh_98/%ED%83%90%EC%83%89

평균 비교 횟수

탐색 성공 : (n + 1)/2번 비교
탐색 실패 : n번 비교
시간 복잡도 : O(n)

코드

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

2. 개선된 순차 탐색

순차 탐색에서 비교횟수는 줄이는 방법
리스트의 끝에 키 값을 저장하고 반복문의 탈출 조건을 키값을 찾을때 까지로 설정
반복문의 키 값의 비교 연산을 줄일 수 있음

https://velog.io/@limsh_98/%ED%83%90%EC%83%89

코드

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

 

 

정렬된 배열에서의 탐색

1. 이진 탐색

데이터가 정렬되어 있는 배열에서 찾고자 하는 값을 비교할 때마다 탐색 범위를 반으로 줄이면서 특정한 값의 위치를 찾는 알고리즘

처음 중간의 값을 임의의 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식
데이터를 삽입, 삭제가 빈번할 시에는 적합하지 않음

https://velog.io/@limsh_98/%ED%83%90%EC%83%89

시간 복잡도

O(logn)

 

2. 색인 순차 탐색

정렬되어있는 자료에 대한 인덱스 테이블(index table)을 사용하여 탐색 효율을 높인 탐색 방법

인덱스 테이블
배열에 정렬되어있는 자료 중에서 일정한 간격으로 떨어져있는 원소들을 저장한 테이블
자료가 저장되어있는 배열의 크기가 n이고 인덱스 테이블의 크기가 m일 때,
배열에서 n/m간격으로 떨어져있는 원소와 그의 인덱스를 인덱스 테이블에 저장 

검색 방법
indexTable[i].key ≤ key < indexTable[i+1].key를 만족하는 i를 찾아서
배열의 어느 범위에 있는지를 먼저 알아낸 후에 해당 범위에 대해서만 순차 검색 수행

https://itdexter.tistory.com/94

 

3. 보간 탐색

정렬된 리스트에서 찾고자 하는 값의 위치를 예측하여 탐색하는 방법

보간 탐색은 이진 탐색과 비슷하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색
사전을 찾을 때 'ㅎ'으로 시작하는 단어는 사전의 뒷부분에서 찾고 'ㄱ'으로 시작하는 단어는 앞부분에서 찾는 것과 유사
데이터가 균등하게 분포(uniformly distributed)되어 있는 자료에 적합

https://jackpot53.tistory.com/35

https://velog.io/@limsh_98/%ED%83%90%EC%83%89

 

시간 복잡도

데이터가 균등하게 분포되어 있는 경우 : O (log log n)
최악의 경우 : O(n)