[Algorithms] 선형 탐색(Linear Search)과 이진 탐색(Binary Search)

하루 하루가 순식간이네요😱

오늘도 학습을 하고

잠을 청해야겠습니다

오늘의 학습 주제는

탐색 알고리즘 중에

가장 단순한 탐색 알고리즘인

선형탐색(Linear search) 혹은

순차탐색(Sequential Search)과

이진탐색(Binary Search)입니다

먼저 선형 탐색은

데이터가 저장되어 있는

배열 또는 선형 리스트를

선두에서부터 하나씩 비교해

찾고자 하는 데이터가

발견될 때까지 검사하는 탐색법입니다

#include <stdio.h>

#define true 1
#define false 0
#define SIZE 100

typedef int index;
typedef int keytype;
typedef int boolean;
typedef char othertype;

index n = -1;

struct array {
    keytype key;
    othertype otherinfo;
};
struct array table[SIZE];

boolean search(keytype target) {
    boolean found = false;
    /* Sentinel method : set sentinel value */
    table[n+1].key = target;
    
    index pos = 0;
    while ( target != table[pos].key ) {
        pos = pos + 1;
    }
    return (found = (pos < SIZE) ? true : false);
}

void insert(keytype x, othertype y) {
    if ( n >= SIZE-1 ) return;
    n = n + 1;
    table[n].key = x;
    table[n].otherinfo = y;
}

void delete(index pos) {
    index i;
    for ( i = pos; i < n - 1; i++ ) {
        table[i] = table[i+1];
    }
    n = n - 1;
}

int main() {
    insert(1, 1);
    insert(2, 2);
    insert(3, 3);
    insert(4, 4);
    printf("result: %d\n", search(3));
}

위의 코드는

일반적인 선형 탐색을

살짝 개량한

보초 기법(Sentinel method)을

사용하였습니다

선형 탐색에서는

탐색하려는 키와

배열상에 있는 데이터가

같은지를 판정하는 연산만

이용하였고

모든 키들을 각각 조사해야해서

효율이 떨어집니다

이번에는 데이터 비교 연산 외에

대소 판정까지 하는

이진 탐색(Binary search)을 보겠습니다

이진 탐색에서는

선형 탐색과 마찬가지로

배열에 레코드를 삽입하지만

반드시 키의 크기 순으로 넣어야 합니다

정렬에 관해서는

추후에 학습하므로 오늘은 생략!

#include <stdio.h>

#define true 1
#define false 0
#define SIZE 100

typedef int index;
typedef int keytype;
typedef int boolean;
typedef char othertype;

index n = -1;

struct array {
    keytype key;
    othertype otherinfo;
};
struct array table[SIZE];

boolean search(keytype target) {
    boolean found = false;
    index right, mid, left;
    left = 0;
    right = n;
    while ( left <= right ) {
        mid = (left + right) / 2;
        if ( target < table[mid].key) right = mid - 1;
        else left = mid + 1;
        printf("left %d right %d mid %d\n", left, right, mid);
    }
    if ( right == -1 ) found = false;
    else found = ( target == table[right].key );
    return found;
}

void insert(keytype x, othertype y) {
    if ( n >= SIZE ) return;
    n = n + 1;
    table[n].key = x;
    table[n].otherinfo = y;
}

void delete(index pos) {
    index i;
    for ( i = pos; i < n - 1; i++ ) {
        table[i] = table[i+1];
    }
    n = n - 1;
}

int main() {
    insert(1, 1);
    insert(2, 2);
    insert(3, 3);
    insert(4, 4);
    printf("result: %d\n", search(2));
}

오늘은 간단하게

선형 탐색과 이진 탐색에 대해

학습하였습니다~😃

그렇게 어렵지 않았던 내용 같네요!

이것으로 이번 학습을 마치겠습니다

그럼 이만-_-