순차탐색과 이진탐색

탐색이란

주어진 자료에서 조건에 해당하는 자료를 찾는 것이다.
자료를 저장하는 방법이나 자료를 정렬하는 방식은 정보를 효율적으로 저장하기 위한 방법이고 탐색은 원하는 정보를 효율적으로 찾기 위한 방법이다.

순차탐색

순차탐색은 탐색하고자 하는 값과 자료들을 검문하는 것처럼 하나씩 비교하며 탐색하는 기법이다.

#include <stdio.h>
int key, count, n, result;
int arr[] = {9, 5, 6, 7, 3, 1, 2};

int search() {
	for (int i = 0; i < n; ++i) {
    	++count;
        if (arr[i] == key) return count; #탐색 성공시 횟수 반환
    }
    return -1; #탐색 실패시 -1 반환
}

int main() {
	n = sizeof(arr)/sizeof(int);
    scanf("%d", &key); #탐색할 값 입력
    result = search();
    if (result == -1) printf("탐색 실패");
    else printf("탐색 성공, 탐색횟수 : %d", result);
  	return 0;
}

위에는 C언어로 구현된 코드이다.
입력받은 값을 자료에서 찾고있다.

이진탐색

자료들을 반씩 쪼개가며 탐색하는 기법이다.
단, 자료들이 반드시 정렬되어있어야 탐색이 가능하다.

#include <stdio.h>
int key, count, n, result;
int arr[] = {9, 5, 6, 7, 3, 1, 2};

int middle;
int search(int start, int end) {
	if (start <= end) {
    	++count;
        middle = (start + end) / 2; #반으로 쪼갠다.
        if (key == arr[middle]) return count; #탐색 성공
        else if (key < arr[middle]) return search(start, middle - 1);
        #찾고자 하는값이 중앙값보다 작기때문에 탐색 범위를 줄인다.
        else if (key > arr[middle]) return search(middle + 1, end);
        #찾고자 하는값이 중앙값보다 크기때문에 탐색 범위를 줄인다.
    }
    return -1; #탐색 실패시 -1 반환
}

int main() {
	n = sizeof(arr)/sizeof(int);
    scanf("%d", &key); #탐색할 값 입력
    result = search(0, n-1);
    if (result == -1) printf("탐색 실패");
    else printf("탐색 성공, 탐색횟수 : %d", result);
  	return 0;
}

위에는 C언어로 구현된 코드이다.
입력받은 값을 자료에서 찾고있다.

순차탐색과 이진탐색의 차이점

두 기법 모두 목표값을 찾는 방법이다, 하지만 순차탐색은 정렬이 되어있지 않은 데이터에도 사용할 수 있는 반면 이진탐색은 정렬된 데이터에서만 사용할 수 있다.

성능은 다음과 같다.