알고리즘 제2 장 실천 실험 보고서 - 2 분 검색 알고리즘 고 쳐 쓰기 - 양가 명
7-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 5
2 4 6 8 10 12
출력 예시:
여기에 상응하는 출력 을 드 리 겠 습 니 다.예 를 들 면:
1 2
먼저 코드 를 첨부 합 니 다.#include
using namespace std;
int search(int a[],int key,int n)
{
int left=0;
int right=n-1;
int i=0;
int j=0;
while (left<=right)
{
int mid=(left+right)/2;
if(key==a[mid])
{
i=j=mid;
cout<
return mid;
}
if(key>a[mid])
{
left=mid+1;
}
else
{
right=mid-1;
}
}
i=right;
j=left;
cout<
return -1;
}
int main()
{
int n;
int x;
cin>>n>>x;
int *a=new int[n];
for(int i=0;i
{
cin>>a[i];
}
search(a,x,n);
return 0;
}
사고방식 과 분석:
알고리즘 은 가장 왼쪽 과 가장 오른쪽 끝 의 수 를 판단 하고 mid 중간 수 를 취한 다.
x 가 배열 의 mid 개수 보다 크 면 left 는 mid + 1 로 변 합 니 다.
x 가 배열 의 mid 개수 보다 작 으 면 right 는 mid - 1 이 됩 니 다.
x 가 배열 의 mid 개수 와 같 을 때 출력 i = j = mid, i, j
크 거나 작은 경우 에는 지역 범 위 를 계속 단축 시 키 고 right 가 left 보다 작 을 때 까지 x 가 현재 배열 에서 오른쪽 개수 와 왼쪽 개수 사이 에 있 는 지 확인 할 수 있 습 니 다. i, j 로 right 와 left 를 출력 할 수 있 습 니 다.
첫 번 째 숫자 라면 출력 0, 0
마침 마지막 숫자 라면 출력 n - 1, n - 1
모든 수 보다 작 으 면 출력 - 1, 0
모든 수 보다 크 면 출력 n - 1, n
시간 복잡 도 O (logn) 공간 복잡 도 O (1)
소감:
이 알고리즘 의 실천 을 통 해 저 는 mid 로 검색 알고리즘 을 처리 할 수 있 는 것 을 배 웠 고 2 분 의 검색 을 했 습 니 다. 판단 조건 과 실행 문 구 를 잘 썼 습 니 다. 처음에 코드 를 다 쓰 고 끝 을 잘 처리 하지 못 했 습 니 다. 나중에 완 선 했 습 니 다. 알고리즘 에 흠 이 생 겼 을 때 초고 지 나 debug 로 한 걸음 한 걸음 문 구 를 실행 하고 잘못된 점 을 찾아내 고 고 고 쳐 야 자신의 전면적 인 물 을 향상 시 킬 수 있 습 니 다.평평 하 다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.