(6)실습6주차_이진탐색+순차자료_[문제1]

알고리즘_6주차.pdf

0.10MB

[문제1]

##이진탐색_순차자료(배열)_노트 :

이론 : 시간복잡도 : O(logN)

 

 

 

##코드 :

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
int* A = NULL;
int result = -1;
 
void BinarySearch(int* A, int start, int end, int key)
{
    //1_ 종료조건★ start > end
    if (start > end)return;
 
    //2_ mid인덱스 저장
    int mid = (start + end) / 2;
 
    //3_A[mid]와 key 비교
 
    if (A[mid] == key) 
    {
        result = mid;
        return;
    }
    else if (A[mid]>key)//key는 왼쪽 구간에 위치
    {
        BinarySearch(A, start, mid - 1, key);
    }
    else {
        result = mid; //★ 현재 mid가 key보다 작으므로 잠정적으로 결과 저장
        BinarySearch(A, mid+1, end, key);
    }
 
}
 
 
int main() 
{
 
    int N,Key;
 
    scanf("%d %d", &N,&Key);
 
    A = (int*)malloc(sizeof(int) * N);
 
    //오름차순으로 입력
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);
 
    BinarySearch(A, 0, N - 1, Key);
 
    printf(" %d", result);
 
    free(A);
 
    return 0;
}