탐색

탐색

사사람들은 항상 무엇인가를 찾아 헤맨다. 예를 들면 출근할 때 입은 옷을 찾는다거나 서랍속의 서류를 찾기도 한다. 텀퓨터에서도 마찬가지다. 실제로 탐색은 컴퓨터가 가장 많이 하는 작업 중의 하나이다. 탐색은 컴퓨터 프로그램에서 가장 많이 사용하는 작업임과 동시에 많은 시간이 요구되므로 탐색을 효율적으로 수행하는 것은 매우 중요하다.

탐색 키

탐색의 단위는 항목이다. 항목은 가장 간단하게는 숫자일 수도 있고 아니면 구조체가 될 수도 있다. 항목 안에는 항목과 항목을 구별시켜주는 키(key)가 존재한다. 이를 탐색키라고 한다. 탐색이란 탐색키와 데이터로 이루어진 여러 개의 항목 주에서 원하는 탐색키를 가지고 있는 항목을 찾는 것이다.

순차 탐색

순차 탐색은 탐색 방법 주에서 가장 간단하고 직접적인 탐색 방법이다. 순차 탐색은 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법이다.

탐색의 태상이 되는 배열은 list[]라고 가정하고 탐색의 범위는 low에서 high까지로 함수의 매개변수로 주어진다. 탐색 함수는 탐색에 성공하면 그 항목이 발견된 위치를 반환하고 그렇지 않으면 -1을 반환하다.

int seq_search(int key, int low, int high) { 
	int i;
	for(i=low; i<=high; i++) { 
		if(list[i]==key)
			return i;  // 탐색 성공
	}
	return -1;    // 탐색 실패
}

[순차 탐색]

• 정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사하는 방법이다.
• 탐색 방법중에서 가장 간단하고 직적접인 탐색방법이다.
• 평균 비교횟수
  • 탐색 성공 : (n + 1) / 2번 비교
  • 탐색 실패 : n번 비교
• 시간 복잡도 : O(n)

개선된 순차 탐색

위의 순차 탐색 프로그램을 살펴보면, 리스트 전체를 탐색하기 위한 반복문에서 리스트의 끝을 테스트하는 비교 연산이 있고 반복문 안에 키 값의 비교 연산이 있다. 리스트의 끝을 테스트하는 비교 연산을 줄이기 위해 리스트의 끝에 찾고자 하는 키 값을 저장하고 반복문의 탈출 조건을 키 값을 찾을 때까지로 설정하도록 수정하면 줄일 수 있다.

int seq_search2(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; // 탐색 성공
}