(11)[Chapter6]이진 탐색(이론 + 코드)

 ## 이론 노트 :

Chapter6_3_이진탐색(이론+코드).pdf

5.72MB

##핵심 내용 요약 :

1_ 구현 코드에서 반띵 기준

• A[mid] > 탐색값 => 왼쪽으로 반띵 => end = mid -1 대입
• A[mid] < 탐색값 => 오른쪽으로 반띵 => start = mid +1 대입
• A[mid] == 탐색값 => 찾았다.=> return mid(인덱스)

2_ 종료 시점까지 도달하는 경우

Case1_▲ 우연히 끝까지 도달한 값 == 탐색 값 => mid 인덱스 반환

Case2_  탐색값이 배열안에 없는 경우 => NULL이 반환

3_ 이진 탐색 기능 : 최악의 경우 (2_상황)

 ※탐색횟수 = [log(2)(탐색 데이터의 수)]

ex_ N = 10 , 최악의 경우의 탐색 횟수 [log(2)(10)] = [3.xxx] = 3번

4_ 이진 탐색 함수 라이브러리 사용법(구조체 배열일 경우) :

ⓐ. compare(람다식 메소드) 작성 : (자세한 내용은 이론노트를 참조해라)

• (1)_ ★const void* 포인터 2개를 구조체 포인터 자료형으로 강제 형변환 + 어느 멤버값으로 정렬할지도 정하기
• (2)_ qsort()로 내림 차순 정렬
• (3)_ ★찾을 탐색 값이 들어간 구조체 변수 하나 선언, 초기화
• (4)_ 탐색 후의 결과를 기록할 포인터 선언
• (5)_ 포인터 <- bsearch((void*)& 3_에서 초기화한 변수,배열포인터, 원소개수, 원소 데이터 크기 , 람다식 Compart ) 

##코드 :

코드1 : 이분탐색 라이브러리 엀이 직접 구현한 코드

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}
 
//_ 이분탐색(재귀x 버전)
int BinarySearch(int* A,int s,int e,int data) 
{
    //매개변수 : 배열 포인터 , start, end 인덱스,찾을 대상 
    //반환값 : 찾았다면, 그 인덱스 반환 , 없다면, -1 반환
 
    int start = s;
    int end = e;
    while (start <= end) {
        //mid 인덱스 구하기
        int mid = (start + end) / 2;
 
        //mid와 탐색 비교
        if (A[mid] < data) //=> 오른쪽 반띵
        {
            start = mid + 1;
        }
        else if (A[mid] > data) //=>왼쪽 반띵
        {
            end = mid - 1;
        }
        else return mid;
 
    }
 
    return -1;
}
 
int main() {
 
    int A[10] = { 11,7,139,871,23,14,1,12,67,672 };
 
    //1_ 내림차순 정렬
    qsort(A, 10, sizeof(int), compare);
 
    printf("(내림차순 후) A배열 :");
    for (int i = 0; i < 10; i++) {
        printf(" %d", A[i]);
    }printf("\n");
 
    //2_ 이분탐색
    int search = 67;
    int result = BinarySearch(A, 0, 9, search);
    
    if (A[result] == search) {
        printf("%d은 A배열에서 %d번째에 있습니다.\n",search,result+1);
    }
    else {
        printf("%d은 A배열에 없습니다.\n", search);
    }
 
    search = 32;
    result = BinarySearch(A, 0, 9, search);
 
    if (A[result] == search) {
        printf("%d은 A배열에서 %d번째에 있습니다.\n", search, result + 1);
    }
    else {
        printf("%d은 A배열에 없습니다.\n", search);
    }
 
    return 0;
}

 

코드2 : 이분 탐색 구조체 배열에서 라이브러리 사용한 코드 예시

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning (disable: 4996)
 
typedef struct _Student {
    int ID;
    char NAME[20];
    double SCORE;
}Student;
 
int Compare(const void* a, const void* b) {
    //자료형 변환
    Student* s1 = (Student*)a;
    Student* s2 = (Student*)b;
 
    if (s1->SCORE > s2->SCORE) {// 2 1
        return 1;
    }
    else if (s1->SCORE < s2->SCORE) {// 1 2 
        return -1;
    }
    return 0;
}
 
int main() {
 
    Student C1[4];
 
    C1[0].ID = 19013219;
    strcpy(C1[0].NAME, "김형준");
    C1[0].SCORE = 3.76;
 
    C1[1].ID = 190234553;
    strcpy(C1[1].NAME, "박정희");
    C1[1].SCORE = 4.21;
 
    C1[2].ID = 19213522;
    strcpy(C1[2].NAME, "전두환");
    C1[2].SCORE = 3.11;
 
    C1[3].ID = 17293449;
    strcpy(C1[3].NAME, "김일성");
    C1[3].SCORE = 1.19;
 
 
    qsort(C1, 4, sizeof(Student), Compare);
 
    for (int i = 0; i < 4; i++) {
        printf("%d %s %.2lf\n", C1[i].ID, C1[i].NAME, C1[i].SCORE);
    }
 
    //bsearch()를 이용해 C1배열 중 SCORE값이 1.19인 값을 찾아 출력한 코드
    Student std;
    std.SCORE = 1.19;
 
    Student* search = bsearch((void*) & std, (void*)C1, 4, sizeof(Student), Compare);
 
    if (search) {
        printf("%d %s %.2lf\n", search->ID, search->NAME, search->SCORE);
    }
    else {//NULL이라면,
        printf("검색 실패\n");
    }
 
    return 0;
}