이분검색과 순차검색 비교

목차

이분검색과 순차검색 비교
■ 검색

■ 실행코드 C

■ 순차 검색(sequential search)

■ 이분 검색

본문내용

과정을 수행하고 가운데 값보다 크면 오른쪽 영역으로 가서 또다시 수행한다. 이를 값을 찾거나 더 이상 분할할 항목이 없을 때까지 반복한다.
void binSearch(int size, const int S[], int target, int &location)
{
int low, high, mid;
low = 0;
high = size - 1;
location = 0;
while((low <= high) && (location == 0))
{
mid = (low + high) / 2;
if(target == S[mid])
location = mid + 1;
else if(target < S[mid])
high = mid - 1;
else
low = mid + 1;
}
}
시간 복잡도: 수학적 귀납법으로 증명
W(n)`=`lgn`+`1
코드설명: 매개변수의 의미는 앞의 순차검색과 같다. while루프의 조건은 더 찾을 항목이 있고(low <= high) 원하는 값을 찾지 못했을 때(location == 0) 계속 반복할지 그만둘지 결정한다. 만약 배열의 중간 값이 찾고자 하는 값(if(target == S[mid]))이면 location변수에 위치를 저장한다. 찾고자 하는 값이 중간 값보다 작으면(else if(target < S[mid])) 배열을 반으로 나눠서 그 왼쪽으로 검색범위를 좁히며 그렇지 않다면 배열의 오른쪽으로 검색범위를 좁혀나간다.
여기서도 seqSearch와 마찬가지로 location에는 검색 실패시 0이 저장되고 그 이외의 값들은 몇 번째 항목에 찾고자하는 값이 들어있는지 알려준다.

키워드

이분검색,   순차검색,   알고리즘,   이진검색,   sequential,   binary,   검색,   search