색인 순차 검색(Index Sequential Search)

색인 순차 검색(Index Sequential Search)

정렬이 되어 있는 자료 중 일정한 간격으로 떨어져 있는 원소를 가지고 있는 인덱스 테이블(Index Table)을 이용하는 순차 검색이다.

배열의 크기가 n이고 인덱스 테이블의 크기가 m일 때, n/m간격으로 떨어져있는 원소와 인덱스를 인덱스 테이블에 저장한다.

찾을 원소를 인덱스 테이블에서 먼저 검색하여 만족하는 범위를 알아낸 후 그 범위에 대해서만 순차 검색을 수행한다.

​

인덱스 테이블의 크기가 작으면 인덱스 테이블에 저장하는 간격이 커지므로 배열에서 검색할 범위도 커진다.

반대로 인덱스 테이블의 크기가 커지면 간격이 작아지므로 배열에서 검색할 범위도 작아진다. 하지만 인덱스 테이블을 검색하는 시간이 늘어난다.

시간 복잡도는 O(m+n/m)이다.

​

예시)

정렬된 배열 = {1, 3, 4, 7, 17, 20, 23, 30, 32}

인덱스 테이블 = {{}, {}, {}}

찾을 원소 = 20

​

1. 검색할 배열의 크기가 9이고 인덱스 테이블의 크기가 3이기 때문에 간격은 9/3인 3으로 정한 후 인덱스 테이블에 해당 간격에 맞는 원소와 인덱스를 저장한다.

​

정렬된 배열 = {1, 3, 4, 7, 17, 20, 23, 30, 32}

인덱스 테이블 = {{0, 1}, {3, 7}, {6, 23}}

​

2. 찾을 원소 20이 포함되는 범위를 인덱스 테이블에서 찾는다.

인덱스 테이블[i] <= 찾을 원소 < 인덱스 테이블[i+1]

즉, 7 <= 20 < 23 이기 때문에 검색할 인덱스 범위를 3 ~ 5로 정한다.

​

정렬된 배열 = {1, 3, 4, 7, 17, 20, 23, 30, 32}

인덱스 테이블 = {{0, 1}, {3, 7}, {6, 23}}

​

3. 검색할 인덱스 범위에 대하여 순차 검색을 수행하여 찾는다.

정렬된 배열 = {1, 3, 4, 7, 17, 20, 23, 30, 32}

​

4. 원소를 찾고 종료한다.

​

프로그램 작성)

package test;

class IndexTable {
	int index;
	int key;
}


class Search {
	IndexTable[] indexTable;
	
	public void indexSequentialsearch(int[] a, int indexTableSize, int key) {
		indexTable = new IndexTable[indexTableSize];
		for(int i=0; i<indexTable.length; i++) {
			indexTable[i] = new IndexTable();
		}
		
		makeIndexTable(a);
		
		int start = 0, end = 0, i = 0;
		for(i=0; i<indexTable.length-1; i++) {
			
			if(indexTable[i].key <= key && key < indexTable[i+1].key) {
				start = indexTable[i].index;
				end = indexTable[i+1].index;
				
				break;
			}
		}
		
		if(i == indexTable.length-1) {
			start = indexTable[i].index;
			end = a.length;
		}
		
		sortedSequentialSearch(a, start, end, key);
	}
	
	public void sortedSequentialSearch(int[] a, int start, int end, int key) {
		int i = 0;
		
		while(i < end && a[i] < key) {
			i++;
		}
		
		if(a[i] == key) {
			System.out.printf("%d 번째 성공! ", (i-start) + 1);
		} else {
			System.out.printf("%d 번째 실패! ", (i-start) + 1);
		}
	}
	
	public void makeIndexTable(int[] a) {
		int interval = a.length / indexTable.length;
		
		if(a.length % indexTable.length > 0) {
			interval++;
		}
		
		for(int i=0; i < indexTable.length; i++) {
			indexTable[i].index = i * interval;
			indexTable[i].key = a[i * interval];
		}
	}
}

public class Test {
	public static void main(String[] args) {
		int[] a = {1, 3, 4, 7, 17, 20, 23, 30, 32};

		System.out.println("정렬 배열 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Search s = new Search();
		s.indexSequentialsearch(a, 3, 20);
		System.out.println();
	}
}

실행 결과)