알고리즘 - 이진탐색 코드를 짜보자(2)

https://shineild-security.tistory.com/26

알고리즘 - 이진탐색 코드를 짜보자(1)

전글에 이어서 오늘은 다른 사용자들의 코드를 참고해서 내 코드도 수정해보는 시간을 가지려고 합니다.

 

 

기존 작성 코드를 우선 살펴보자.

 

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int num;
    printf("데이터 개수 입력 : ");
    scanf("%d", &num);
    int data[num];
    for (int i = 0; i < num; i++){
        printf("데이터 입력: ");
        scanf("%d", (data + i));
    }
    int tmp;
    for (int n = 0; n < num; n++){
        for (int i = n+1; i < num; i++){
            if (data[n] > data[i]){
                tmp = data[n];
                data[n] = data[i];
                data[i] = tmp;
            }
        }
    }
    int n = num/2;
    int find;
    printf("찾고자 하는 숫자 : ");
    scanf("%d", &find);
    while(1){
    
        if (data[n] == find){
            printf("%d번째에 %d가 들어있습니다.\n", n+1, find);
            break;
        }
        else if (data[n] > find){
            n = n/2;
        }
        else if (data[n] < find){
            n = (n/2) + n;
        }
    }
    return 0;
}

 

인터넷으로 찾아본 결과 대부분 비슷한 형식으로 작성하였던데 알고보니 위키백과에 적혀있었다.

그래서 위키백과에서 작성된 코드를 참고하도록 하였다.

 

def binarySearch(array, value, low, high):
	if low > high:
 		return False
 	mid = (low+high) / 2
 	if array[mid] > value:
 		return binarySearch(array, value, low, mid-1)
 	elif array[mid] < value:
 		return binarySearch(array, value, mid+1, high)
 	else:
 		return mid

위키백과에서는 파이썬으로 만들어져있습니다.

 

그리고 최소값과 최대값을 지정하여서 재귀함수로 계속 최소값과 최대값을 변경하며 탐색을 진행하며 최소로 지정한 값이 최대값을 뛰어 넘을 때 false를 리턴하게 설계되었습니다.

즉 검색하고자 하는 데이터가 존재하지 않을 때의 탈출문인데 저는 이것이 빠져있었습니다.

그래서 다른건 딱히 참고하지 않아도 되겠다 싶어서 예외문만 추가해주고 최종 수정을 마무리 지었습니다.

 

 

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int num;
    printf("데이터 개수 입력 : ");
    scanf("%d", &num);
    int data[num];
    for (int i = 0; i < num; i++){
        printf("데이터 입력: ");
        scanf("%d", (data + i));
    }
    int tmp;
    for (int n = 0; n < num; n++){
        for (int i = n+1; i < num; i++){
            if (data[n] > data[i]){
                tmp = data[n];
                data[n] = data[i];
                data[i] = tmp;
            }
        }
    }
    int n = num/2;
    int find;
    printf("찾고자 하는 숫자 : ");
    scanf("%d", &find);
    while((1<=n) & (n<=num)){
    
        if (data[n] == find){
            printf("%d번째에 %d가 들어있습니다.\n", n+1, find);
            break;
        }
        else if (data[n] > find){
            n = n/2;
        }
        else if (data[n] < find){
            n = (n/2) + n;
        }
    }
    return 0;
}

while에 조건만 걸어두었습니다.

좀더 다양한 구문들을 보고싶었지만 배열을 이진탐색하는 코드는 low와 high를 이용한 것말고는 없어서 아쉬웠습니다.