순차탐색과 이진탐색

순차탐색 : 특정한 원소를 찾기 위해 순차적으로 하나씩 탐색하는 방법

#define _CRT_SECURE_NO_WARNONGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LENGTH 100

char **array;
int founded; // 특정원소 발견 관련 변수


int main(void)
{
	char *word;
    word = malloc(sizeof(char) * LENGTH); // 찾을 단어에 대해 공간 할당
    scanf("%d %s", &n , word); // 전체 데이터 개수, 문자개수
    array = (char**) malloc(sizeof(char*) * n); 
    for (int i =0;i<n;i++)
    {
        array[i] = malloc(sizeof(char) * LENGTH);
        scanf("%s", array[i]);
    }
    //0부터 탐색을 하겠다
    for (int i = 0; i<n;i++)
    {
        if (!strcmp(array[i], word))
        {
            printf("%d번째 원소입니다..\n",i+1);
            founded = 1;
        }
    }
    if (!founded)
        printf("원소를 찾을 수 없습니다.\n");
    system("pause");
    return 0;
}

가장 앞에 있는 데이터부터 탐색하므로, 시간복잡도는 O(n)이다.

 

이진탐색 : 데이터가 이미 정렬되어 있는 상황에서 사용가능한 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색함. 시간복잡도는 O(logN)의 시간복잡도를 가지게 된다.

 

#define _CRT_SECURE_NO_WARNONGS
#include <stdio.h>
#define MAX_SIZE 100000

int a[MAX_SIZE];
int founded = 0;

int search(int start, int end, int target){
	if(start>end)
        return -9999;
        
    int mid = (start + end) / 2; 
    if(a[mid] == target)
        return mid;
    else if (a[mid]>target)
        retrun search(start, mid-1, target)
    else
        retrun search(mid+1, end, target);
}

int main(void){
    int n, target;
    scanf("%d %d", &n, &target);
    for(int i=0;i<n;i++) scanf("%d", &a[i]);
    int result= search(0,n-1, target);
    if(result != -9999) printf("%d번째 원소입니다.\n", result+1);
    else printf("원소를 찾을 수 없습니다.\n");
    system("pause");
    return 0;


}