알고리즘 제2 장 실천 실험 보고서 - 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 로 한 걸음 한 걸음 문 구 를 실행 하고 잘못된 점 을 찾아내 고 고 고 쳐 야 자신의 전면적 인 물 을 향상 시 킬 수 있 습 니 다.평평 하 다