PTA | 01 - 복잡 도 3 2 분 찾기 (20 분) 2 분 찾기

이 문 제 는 이분 검색 알고리즘 을 실현 해 야 한다.
함수 인터페이스 정의:
Position BinarySearch( List L, ElementType X );

그 중에서 List 구 조 는 다음 과 같다.
typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /*                 */
};

L 은 사용자 가 들 어 오 는 선형 표 입 니 다. 그 중에서 Element Type 요 소 는 >, =,
심판 테스트 프로그램 샘플:
#include 
#include 

#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /*                 */
};

List ReadInput(); /*     ,    。     1     */
Position BinarySearch( List L, ElementType X );

int main()
{
    List L;
    ElementType X;
    Position P;
    L = ReadInput();
    scanf("%d", &X);
    P = BinarySearch( L, X );
    printf("%d
", P); return 0; } /* */

입력 샘플 1:
5
12 31 55 89 101
31

출력 예시 1:
2

입력 샘플 2:
3
26 78 233
31

출력 예시 2:
0

코드 구현
Position BinarySearch( List S, ElementType K )
{	
	int left=1;
	int right=S->Last;	
	if(S==NULL)
		return NotFound;	
	while (left <= right) {
        int mid = (left + right) / 2;  		      
        if(S->Data[mid]==K)
        	return mid;
       	else if(S->Data[mid]>K)
       		right=mid-1;
		else 
			left=mid+1;
	}	
}

좋은 웹페이지 즐겨찾기