이진탐색

  • 이진탐색(Binary Search)은 배열 내부 데이터가 이미 정렬 되어 있는 상황에서 사용 가능한 알고리즘이다.
  • 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.
  • 한 번 확인할 때마다 보아야 하는 원소의 개수가 절반씩 줄어든다는 점에서 탐색 시간이 O(logN)의 시간 복잡도를 가진다.
    image.png

image.png

image.png

image.png

image.png

이진탐색 구현

#include<stdio.h>
#define MAX_SIZE 10000

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); //mid를 기준으로 왼쪽 부분
    else return search(mid+1,end,target); //mid를 기준으로 오른쪽 부분
}

int main() {
    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;
}