데이터 구조 01 - 복잡 도 3 2 분 찾기

8280 단어 데이터 구조데이터 구조 (저장 성)
이 문 제 는 이분 검색 알고리즘 을 실현 해 야 한다.
함수 인터페이스 정의:
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
분석 하 다.
이 문 제 는 2 분 검색 알고리즘 을 쓰 는 함수 인터페이스의 기본 적 인 사고방식 에 문제 가 없다 는 것 이다. 찾 아야 할 값 과 현재 범위 내의 중간 값 을 비교 하면 세 가지 상황 이 있다.
  • 찾 으 려 는 목표치 < 중간 값, 중간 값 의 오른쪽 부분 을 버 리 고 범위 축소
  • 찾 으 려 는 목표치 > 중간 값, 중간 값 왼쪽 부분 을 버 리 고 범 위 를 축소
  • 찾 아야 할 목표치 = 중간 값 을 찾 으 면 찾 을 수 있 지 않 습 니까? 결 과 를 바로 되 돌려 줍 니 다
    • 이 검색 은 순환 횟수 가 불확실 한 순환 이기 때문에 while 로 순환 을 뛰 어 내 리 는 조건 은:
  • 위의 세 번 째 상황 을 찾 았 습 니 다. 바로 return 하면 됩 니 다
  • 다 찾 았 습 니 다. 아 닙 니 다!왼쪽 범 위 를 정 하 는 값 이 오른쪽 범 위 를 정 하 는 값 보다 크 면 (같 으 면?) 이미 찾 았 음 을 나타 내 고 이때 NotFound
    • 로 돌아 갑 니 다.
    코드 (cpp)
    Position BinarySearch( List L, ElementType X ){
	Position left = 1;
	Position right = L->Last;
	while(left<=right){  //            ？
		Position center = (left+right)/2;  //      
		if(L->Data[center] < X){     //     ，X      
			left = center+1;
		}else if(X < L->Data[center]){   //     ，X      
			right = center-1;
		}else  //   ，     
			return center;
	}
	return NotFound;
}

    매번 범 위 를 절반 으로 줄 이기 때문에 그 복잡 도 는 O (l g n) O (lgn) O (lgn) 이다.
    초 상세 자바 접속 ping + 결제 (취 합 결제)
    항목 내용 세분 화

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage