[알고리즘] 순차탐색 / 이분탐색

예제 : 임의의 수 x 찾기

문제: 크기가 n인 배열 S에 x가 있는가?

• 입력(파라미터): (1) 양수 n, (2) 배열 S[1..n], (3) 키 x
• 출력: x의 위치, 만약 없으면 0.
• 알고리즘(자연어):
• x와 같은 원소를 찾을 때까지 S에 있는 모든 원소를 차례로 검사한다.
• 만일 x 와 같은 원소를 찾으면 S 에서의 그 위치를, S 를 모두 검사하고도 찾지 못하면 0을 내준다

1. 순차 탐색

void seqsearch(int n,              // 입력(1)
								const keytype S[], // (2)
								keytype x,         // (3)
								index& location) { // 출력
	location = 1;
	while (location <= n && S[location] != x)
		location++;
	if (location > n)
		location = 0;
}

• while-루프: 아직 검사할 항목이 있고, x를 찾지 못했나?
• if-문: 모두 검사하였으나, x를 찾지 못했나?

사색

• 순차검색 알고리즘으로 키(key)를 찾기 위해서 S에 있는 항목을 몇 개 검색해야 하는가? √ key와 같은 항목의 위치에 따라 다름 √ 최악의 경우: n → 모든 배열의 원소를 다 확인할 경우
• 좀 더 빨리 찾을 수는 없는가? √ S에 있는 항목에 대한 정보가 없는 한 더 빨리 찾을 수 없다. ex) S 의 정렬 방식 등 .

2. 이분탐색

void binsearch(int n, // 입력(1)
								const keytype S[], // (2)
								keytype x, // (3)
								index& location) // 출력
	{ index low, high, mid;
		low = 1; high = n;
		location = 0;
		while (low <= high && location == 0) 
			{ mid = (low + high) / 2; // 정수나눗셈
			if(x == S[mid]) 
				location = mid;
			else if (x < S[mid]) 
				high = mid – 1;
			else low = mid + 1;
	}
}

• while-루프: 아직 검사할 항목이 있고, x를 찾지 못했나?

사색

• while 문을 수행할 때마다 검색 대상의 총 크기가 1/2 씩 감소하기 때문에 최악의 경우라도 logn + 1개만 검사하면 된다

순차탐색 VS 이분탐색