[자료구조] Search(탐색) - 순차탐색과 이진탐색

1. 순차탐색(Sequential search)

: 정렬되지 않은 배열의 항목들을 처음부터 끝까지 하나씩 검사해 원하는 항목을 찾는 방법

 

구현 원리는 다음과 같다.

low에서 high까지 key와 비교하고 탐색에 성공하면 위치를 반환, 실패하면 -1 반환

 

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

 

역순으로 정렬되어 있는 최악의 경우에 n개의 데이터를 n번 검사해야 하므로 시간복잡도는 O(n)이다.

 

 

---

 

2. 이진탐색(Binary Search)

: 배열의 중앙에 있는 값을 검사해 찾고자 하는 값이 오른쪽인지 왼쪽인지 알아내는 방법

 

구현 원리는 다음과 같다.

배열의 중앙값과 찾고자 하는 값을 비교한다.
  - 중앙값 > 찾고자 하는 값 : 찾고자 하는 값이 배열의 왼쪽에 존재
  - 중앙값 < 찾고자 하는 값 : 찾고자 하는 값이 배열의 오른쪽에 존재

 

 

먼저 이진 탐색을 순환적으로 구현하면 다음과 같다.

int BSearch(int key, int low, int high) {
	int mid;
    	if (low <= high) {
        	mid = (low + high) / 2;
            	if (key == list[mid])
                	return mid;
                else if (key > list[mid])
                    	return BSearch(key, low, mid-1);
                else
                	return BSearch(key, mid+1, high);
        }
     	return -1;
}

 

 

다음으로 반복적으로 구현한 코드이다.

int BSearch(int key, int low, int high) {
	int mid;
    while (low <= high) {
    	mid = (low + high) / 2;
        if (key == list[mid])
        	return mid;
        else if (key > list[mid])
        	low = mid + 1; 
        else
            high = mid - 1;
    }
    return -1;
}

 

이진 탐색은 반복할 때마다 탐색 범위가 반으로 줄어들기 때문에 시간 복잡도는 O(logn)이다.

 

 

---

참고

C언어로 쉽게 풀어쓴 자료구조