[C언어 이진탐색 알고리즘] 이진탐색 구현하기

💡 이번에는 이진탐색을 구현 하는 법을 배워보았다.

문제

💡 이진탐색 기능으로 원소를 탐색하시오.

당연히 없는 문제기에 대충 내가 만들었다.

해답

#define _CRT_SECURE_NO_WARNINGS
#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) {
        return search(start, mid - 1, target);
    } else {
        return 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");
    }

    return 0;
}

설명

순차 탐색이란?

이진 탐색(Binary Search)은 배열 내부 데이터가 이미 정렬되어있는 상황에서 사용 가능한 알고리즘이다.

탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.

𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다.

search 함수

int search(int start, int end, int target) {
    if (start > end) { // start가 end보다 클 수는 없기 때문에 큰 경우 return -9999; 해준다.
        return -9999;
    }

    int mid = (start + end) / 2;

    if (a[mid] == target) {   // 반으로 나눈 인덱스 값이 타겟과 같을 때
        return mid;
    } else if (a[mid] > target) {   // 찾고자하는 값이 작을때
        return search(start, mid - 1, target);
    } else {
        return search(mid + 1, end, target);
    }
}

• 반으로 나눠서 탐색하기 때문에 int mid = (start + end) / 2; 에서 인덱스 값을 반으로 나누는 것을 볼 수 있다.
• search(start, mid - 1, target); 와 search(mid + 1, end, target); 에서 mid에 -1과 +1을 해주는 이유
  • a[mid] == target 에서 이미 검사를 한번 했기 때문에 또다시 검사할 필요 없기 때문에 mid에 -1과 +1을 해준다.

---

마치며..

순차 탐색과 마찬가지로 이진 탐색도 어렵지 않게 이해해 볼 수 있었다.