본문 바로가기

이글루스

programming

검색페이지 이동

사이드 메뉴

이글루스 블로그 정보

[C언어]이진탐색 알고리즘

앱으로 보기

본문 폰트 사이즈 조절

이글루스 블로그 컨텐츠

#include <stdio.h>
int bsearh(int ar[]int lenint target);
int main()
{
    int arr[] = {13579}; 
    int idx;
    idx = bsearh(arr, sizeof(arr) / sizeof(int), 7);
    if (idx == -1)
        printf("탐색 실패");
    else
        printf("타겟이 저장된 인덱스: %d\n", idx);
}
int bsearh(int arr[]int lenint target)
{
    int first = 0;
    int last = len - 1;
    int mid;
    while (first <= last)
    {
        mid = (first + last) / 2;
        if (target == arr[mid])
            return mid;
        else if (target < arr[mid])
            last = -mid - 1//
        else
            first = mid + 1//
    }
    return -1;
}

이진탐색 알고리즘은 순차 탐색보다 더 좋은 성능을 보인다.
하지만 알고리즘을 적용하기 위해서는 배열에 저장된 데이터가 정렬된 상태이어야만 한다.
위의 프로그램의 설명을 시작하겠다.

루프 1:
배열 인덱스의 시작과 끝을 더하고 나눈다. 여기서는 (0+4)/2
나눠서 얻은 결과 2를 인덱스 값으로 하여 arr[2]에 저장된 값이 7인지를 확인한다.(타겟을 7로 지정함)
만약 아니면 arr[2]에 저장된 값과 타겟의 대소를 비교한다.
arr[2]<7 이므로 범위를 인덱스 3~4로 줄인다.

루프 2:
(3+4)/2을 계산한다. 나머지는 버려서 3이 나온다.
arr[3]에 저장된 값이 7이 맞는지 확인한다.
7이므로 여기서 루프 종료.

이진 탐색은 탐색의 대상을 반씩 줄여나간다.
따라서 무작정 처음부터 끝까지 비교하는 순차 탐색보다 좋은 성능을 보인다.

알고리즘을 이해하는데 가장 쉬운 방법은 머리로 시뮬레이션을 돌려보는 거다.
그렇다기 보다는 그렇게 해야 이해할 수 있다.

포스트 공유하기

썸네일
frogrammer님의 글 구독하기
덧글 0 관련글(트랙백) 0
신고
맨 위로
앱으로 보기 배너 닫기

공유하기

주소복사

아래의 URL을 길게 누르면 복사할수있습니다.

http://frogrammer.egloos.com/m/6536881
닫기

팝업

모바일기기에서만 이용이 가능합니다.
운영체제가 안드로이드, ios인
모바일 기기에서 이용해주세요.

덧글 삭제

정말 삭제하시겠습니까?

비밀번호 확인

게시글 신고하기

밸리 운영정책에 맞지 않는 글은 고객센터로
보내주세요.

신고사유


신고사유와 맞지 않을 경우 처리되지 않을 수 있습니다.
저작권 위반/명예훼손 등은 고객센터를 통해 권리침해
신고해주세요.
고객센터 바로가기