01 - 복잡 도 32 점 찾기 (20 점) -- 출처: PTA

데이터 구조 연습 문제 01 - 복잡 도 3 2 점 찾기 (20 점)
이 문 제 는 이분 검색 알고리즘 을 실현 해 야 한다.
함수 인터페이스 정의:

Position BinarySearch( List L, ElementType X );

List 구조 정 의 는 다음 과 같다.

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

L 은 사용자 가 입력 한 선형 표 입 니 다. 그 중에서 Element Type 요 소 는 >, =, Binary Search 를 통 해 X 가 Data 에 있 는 위 치 를 찾 을 수 있 습 니 다. 즉, 배열 아래 에 표 시 됩 니 다 (주의: 요 소 는 아래 표 1 부터 저장 합 니 다).찾 으 면 다음 표 시 를 되 돌려 줍 니 다. 그렇지 않 으 면 특수 한 실패 표시 NotFound 를 되 돌려 줍 니 다.
심판 테스트 프로그램 샘플:

#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

문 제 는 아래 와 같다.
실제로 Binary Search 함수 부분의 코드 만 제출 하고 이 부분 은 의심 합 니 다.샘플 1 을 입력 할 때 얻 은 결 과 는 3 으로 샘플 1 의 출력 과 일치 하지 않 습 니 다.만약 개선 의견 이 있 으 면 독자 가 얼마든지 제기 해 주시 기 바 랍 니 다.

Position BinarySearch(List L, ElementType X)
{
    ElementType l = 1;
    ElementType r = L->Last;
    int mid = 1;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (X == L->Data[mid])
        {
            return mid;
        }
        else if (L->Data[mid] > X)
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    return NotFound;
}

전체 코드 는 다음 과 같다.

#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;
}
List ReadInput()
{
    int length;
    scanf("%d", &length);
    ElementType a;
    int i = 1;
    List list;
    list = (List)malloc(sizeof(struct LNode));
    while (i <= length)
    {
        scanf("%d", &a);
        list->Data[i] = a;
        list->Last = i;
        i++;
    }
    return list;
}
Position BinarySearch(List L, ElementType X)
{
    ElementType l = 1;
    ElementType r = L->Last;
    int mid = 1;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (X == L->Data[mid])
        {
            return mid;
        }
        else if (L->Data[mid] > X)
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    return NotFound;
}