2 점 찾기 가 그렇게 쉬 워 요? -알고리즘 제2 장 온라인 실천 보고서
2 분 검색 알고리즘 바 꾸 기 (20 분 하 다
제목 출처:, 왕 샤 오 둥
a [0: n - 1] 은 정렬 된 배열 입 니 다. 2 분 검색 알고리즘 을 바 꾸 어 x 가 배열 에 없 을 때 x 보다 작은 최대 요소 위치 i 와 x 보다 큰 최소 요소 위치 j 를 되 돌려 주 십시오.검색 요소 가 배열 에 있 을 때 i 는 j 와 같 고 모두 x 가 배열 에 있 는 위치 입 니 다.
입력 형식:
두 줄 입력:
첫 번 째 줄 은 n 값 과 x 값 입 니 다.두 번 째 줄 은 n 개의 서로 다른 정수 로 구 성 된 비 내림차 순 으로 모든 정수 간 에 빈 칸 으로 구분 된다.
출력 형식:
x 보다 작은 최대 요소 의 최대 하 표 i 와 x 보다 큰 최소 요소 의 최소 하 표 j 를 출력 합 니 다.검색 요소 가 배열 에 있 을 때 i 는 j 와 같 습 니 다.알림: x 가 모든 수치 보다 작 으 면 출력: - 10 x 가 모든 수치 보다 크 면 출력: n - 1 의 값 n 의 값
입력 예시:
여기에 입력 그룹 을 드 립 니 다.예 를 들 면:
6 52 4 6 8 10 12출력 예시:
여기에 상응하는 출력 을 드 리 겠 습 니 다.예 를 들 면:
1 2둘째, 문제 설명
2 분 검색 알고리즘 개선 은 이미 정렬 된 배열 로 알려 져 있 습 니 다. 입력 한 데이터 x 에 대해 개 선 된 2 분 검색 알고리즘 을 통 해 x 가 주어진 배열 보다 큰 (배열 오른쪽) 인지 작은 (배열 왼쪽) 인지, 크기 가 배열 안에 있 는 지 판단 합 니 다.배열 에 x 가 있 으 면 x 가 있 는 배열 의 아래 표 시 를 출력 합 니 다. 그렇지 않 으 면 x 보다 작은 최대 숫자의 아래 표 시 를 출력 하고 x 보다 큰 최소 숫자의 아래 표 시 를 출력 합 니 다.
2 분 검색 은 x 가 배열 에 있 는 배열 아래 표 시 를 찾 을 수 있 습 니 다. 이 를 개선 하면 x 가 배열 에 없 는 상황 에서 결 과 를 얻 을 수 있 습 니 다.
셋째, 알고리즘 설명
1、 if(x else if(x>a[n-1]) cout< else BinarySearch(a,x,n); x 가 배열 보다 큰 지, 배열 보다 작은 지 판단 합 니 다. 중간 에 있 으 면 개 선 된 2 분 검색 알고리즘 을 호출 합 니 다. 2. 2 분 검색 (개선) void BinarySearch(int a[],int x,int n){ int left = 0; int right = n-1; int flag=0; while (left <= right){ int middle = (left+right)/2; if (x == a[middle]){ cout< return ; } if (x > a[middle]){ left = middle+1; } else { right = middle-1; } } if(a[left]>x) cout< else if(x>a[left]) cout< return; } 배열 의 양 끝 숫자 left, right 를 가 져 옵 니 다. left 가 right 보다 작 을 때 배열 이 존재 하고 하나의 요소 가 아 닙 니 다. 배열 의 중간 에 있 는 숫자 (중위, 정렬 됨) 를 순환 적 으로 구 합 니 다. 만약 에 이 중간 에 있 는 숫자 가 x 라면 x 의 작은 표 지 를 직접 출력 합 니 다. 그렇지 않 으 면 범 위 를 축소 합 니 다.(반반 으로 줄 이 고 x 가 중간 수 보다 크 면 이 함 수 를 재 귀적 으로 호출 하고 범 위 는 중간 수 에서 right 로 바 꾸 며 반대로 호출 범 위 는 left 에서 중간 수의 이 2 분 알고리즘 으로 바 꿉 니 다). 배열 되 어 있 는 배열 이기 때문에 x 가 배열 에 없 으 면 x 는 배열 에서 좌우 양쪽 의 숫자 가 요구 하 는 답 입 니 다. 따라서 2 분 알고리즘 이 멈 추 었 을 때 현재 'left' 와 비교 하면 됩 니 다.의 그 숫자 와 x 의 크기 는 x 보다 큰 최소 수 와 x 보다 작은 최대 수의 배열 아래 표 시 를 확정 할 수 있 습 니 다. 만약 left 가 x 보다 크다 면 그 두 수 는 left 와 left - 1 이 고, 반대로 left 와 left + 1 입 니 다. 넷, 알고리즘 시간 및 공간 복잡 도 분석 void BinarySearch (int a[],int x,int n){ int left = 0; int right = n-1; int flag=0; while (left <= right){ int middle = (left+right)/2; if (x == a[middle]){ cout< return ; } if (x > a[middle]){ left = middle+1; } else { right = middle-1; } } if(a[left]>x) cout< else if(x>a[left]) cout< return; } 2 분 검색 알고리즘 시간 복잡 도 분석: 데이터 의 규 모 를 N (즉, 호출 할 때마다 right - left) 이 라 고 가정 하고 프로그램 이 실행 하 는 비교 횟수 는 C (N) 로 표시 합 니 다. 프로그램 이 존재 하지 않 는 데 이 터 를 찾 았 다 고 가정 하면 이때 실행 하 는 횟수 가 가장 많 습 니 다. 첫 번 째 실행 시: (1. x 와 a [middle] 의 비 교 를 한 번 수행 하 는 것 을 의미 합 니 다. (N / 2) 다음 에 이 알고리즘 을 호출 할 때 right - left 의 값, 즉 새로운 데이터 규모 가 매번 절반 이 적은 것 을 의미 합 니 다) 총 n 개의 원소 가 있다 고 가정 하면 2 분 후에 매번 찾 는 구간 의 크기 는 n, n / 2, n / 4,..., n / 2 ^ k (다음 작업 원소 의 나머지 개수) 이 고 그 중에서 k 는 순환 하 는 횟수 입 니 다. 최 악의 경 우 는 K 차 2 분 후에 각 구간 의 크기 를 1 로 나 누 어 원 하 는 원 소 를 찾 을 수 있 습 니 다. n / 2 ^ k = 1 k = log2n 을 얻 을 수 있 기 때문에 시간 복잡 도 는 O () = O (logn) 를 나 타 낼 수 있다. 이분 검색 알고리즘 공간 복잡 도 분석: 교체 하 는 알고리즘 을 사용 하여 원래 의 배열 에서 시작 하여 이 배열 의 범 위 를 순환 적 으로 바 꾸 고 다른 보조 공간 을 신청 하지 않 았 기 때문에 공간 복잡 도 는 상수 등급 으로 O (1) 이다. 다섯, 체험 2 분 검색 코드 를 만 드 는 것 은 어렵 지 않 습 니 다. 간단 하고 기본 적 인 알고리즘 입 니 다. 이 문 제 는 개선 하기 어렵 습 니 다. 규칙 을 발견 해 야 합 니 다. x 가 배열 에 없 을 때 x 보다 작은 최대 수 와 x 보다 큰 최소 수 는 2 분 마지막 으로 가리 키 는 요소 와 왼쪽 또는 오른쪽 입 니 다. 배열 이 질서 있 는 서열 이기 때 문 입 니 다. 처음에 2 분 검색 프레임 워 크 를 만 든 다음 상황 을 나 누 었 습 니 다.이것 을 생각 하고 실현 하 는 데 시간 이 좀 걸 렸 고 처음에 친 코드 가 매우 복잡 했다. 사실은 많은 부분 이 수 다스 럽 고 반복 적 인 조작 이 었 다. 선생님 의 알림 에 쓸모없는 코드 를 삭제 하고 개선 한 후에 매우 상쾌 했다. 그래서 코드 를 만 드 는 것 은 어렵 지 않 습 니 다. 문 제 를 해결 하 는 방법 에 대해 생각 하기 어렵 습 니 다. 그리고 코드 를 만 든 후에 자신 이 만 든 코드 를 몇 번 더 보고 모든 줄 이 무엇 을 하 는 지, 어떤 변화 와 쓸모 가 있 는 지, 자신 도 어 지 럽 게 보 는 것 은 좋 지 않 은 해결 방법 입 니 다. 그래 야 처음으로 만 든 코드 를 개선 하고 간소화 할 수 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
