PTA - 데이터 구조 - 01 - 복잡 도 3 2 점 찾기 (20 점)

7439 단어 데이터 구조
이 문 제 는 이분 검색 알고리즘 을 실현 해 야 한다.
함수 인터페이스 정의: Position BinarySearch (List L, Element Type X);그 중에서 List 구 조 는 다음 과 같다.
typedef int Position; typedef struct LNode List; struct LNode {Element Type Data [MAXSIZE]; Position Last; / 선형 표 의 마지막 요소 의 위치 저장 * /};L 은 사용자 가 들 어 오 는 선형 표 입 니 다. 그 중에서 Element Type 요 소 는 >, =,
입력 샘플 1: 5 12 31 55 89 101 31 출력 샘플 1: 2 입력 샘플 2: 3 26 78 233 31 출력 샘플 2: 0
사고방식 의 이분 탐색 원 리 는 어렵 지 않다. 원래 현실 은 다음 과 같다.
Position BinarySearch( List L, ElementType X )
{
    ElementType * dataset = L->Data;
    int end = L->Last;
    int start = 0;

    while((end - start) > 1)
    {
        int mid = (start + end)/2;

        if (dataset[mid] == X)
        {
            return mid;
        }
        else if (dataset[mid] < X)
        {
            start = mid;
        }
        else // dataset[mid] > X
        {
            end = mid;
        }
        
        //    ,      ,           
        if (dataset[start] == X)
        {
        	return start;
		}
		else if (dataset[end] == X)
		{
			return end;
		}
    }

    return NotFound;
}

그러나 너무 수다스럽다. 주로 start 와 end 위치의 값 을 판단 해 야 하기 때문에 다른 사람의 답 을 겨냥 했다.
Position BinarySearch( List L, ElementType X )
{
    ElementType * dataset = L->Data;
    int end = L->Last;
    int start = 0;

    while(start <= end)
    {
        int mid = (start + end)/2;

        if (dataset[mid] == X)
        {
            return mid;
        }
        else if (dataset[mid] < X)
        {
            start = mid + 1;  	//   start   end     ,     
        }
        else // dataset[mid] > X
        {
            end = mid - 1;
        }
    }

    return NotFound;
}

좋은 웹페이지 즐겨찾기