[데이터 구조 와 알고리즘] 92 점 찾기

[데이터 구조 와 알고리즘] 92 점 찾기
정렬 된 데이터 에 적용 합 니 다. 예 를 들 어:

    int array[] = {1,2,3,6,7,8,9};

의 원리
2 분 검색 은 절반 검색 이 라 고도 부 르 는데 장점 은 비교 횟수 가 적 고 검색 속도 가 빠 르 며 평균 성능 이 좋다 는 것 이다.검사 대기 표 가 질서 있 는 표 이 고 삭제 가 어렵 다 는 단점 이 있다.따라서 반절 찾기 방법 은 자주 변동 하지 않 고 빈번 한 서열 표를 찾 는 데 적용 된다.먼저, 표 의 요 소 는 오름차 순 으로 배열 되 고 표 중간 위치 에 기 록 된 키 워드 를 검색 키워드 와 비교 하 며 이들 이 같 으 면 성공 적 으로 찾 을 수 있다 고 가정 합 니 다.그렇지 않 으 면 중간 위치 기록 을 이용 하여 시 계 를 앞, 뒤 두 개의 서브 시트 로 나 누고 중간 위치 기록 의 키워드 가 키 워드 를 찾 는 것 보다 크 면 앞의 서브 시트 를 찾 고 그렇지 않 으 면 뒤의 서브 시트 를 찾 습 니 다.이상 의 과정 을 반복 합 니 다. 조건 을 만족 시 키 는 기록 을 찾 아 검색 에 성공 하거나 하위 표 가 존재 하지 않 을 때 까지 찾 을 수 없습니다.
만약 우리 가 지금 배열 에 8 (key) 이라는 수치 가 존재 하 는 지 찾 으 려 고 한다 면.먼저 배열 의 중간 수 6 을 찾 아 6 과 8 을 비교 하고 6 대 8 이 작 기 때문에 배열 의 오른쪽 에서 2 분 검색 을 하면 매번 절반 의 길 이 를 줄 일 수 있 는 배열 의 길 이 를 찾 을 수 있다.
순환 을 실현 하 다

#include <iostream>
using namespace std;

template <class T>
int getArrayLen(T& array){
    return sizeof(array) / sizeof(array[0]) ;
}


template <class T>
int binary_search (T& array , int key , int begin , int end){
    if(begin >= end)
        return -1;
    int middle = (begin+end) / 2;
    if(array[middle] > key)
        return binary_search(array , key , begin , middle);
    else if(array[middle] < key)
        return binary_search(array , key , middle + 1 , end);
    else
        return middle;
}


int main(){
    int i=-2 , array[] = {0,1,2,3,6,7,8,9};
    for(;i<15;i++)
        cout << "searching : " << i <<  "\t\t position : " << binary_search(array , i , 0 , getArrayLen(array)) << endl;
    return 0;
}

결실

searching : -2       position : -1
searching : -1       position : -1
searching : 0        position : 0
searching : 1        position : 1
searching : 2        position : 2
searching : 3        position : 3
searching : 4        position : -1
searching : 5        position : -1
searching : 6        position : 4
searching : 7        position : 5
searching : 8        position : 6
searching : 9        position : 7
searching : 10       position : -1
searching : 11       position : -1
searching : 12       position : -1
searching : 13       position : -1
searching : 14       position : -1
Program ended with exit code: 0

시간 복잡 도
T(n)=T(2/n)+O(1) O(logN)
공간 복잡 도
logN
2 차 교 체 를 실현 하 다

#include <iostream>
using namespace std;

template <class T>
int getArrayLen(T& array){
    return sizeof(array) / sizeof(array[0]) ;
}


template <class T>
int binary_search_iterative(T& array, int key, int begin, int end){
    int middle ;
    while(begin < end){
        middle = (begin+end) / 2;
        if(array[middle] > key)
            end = middle;
        else if(array[middle] < key)
            begin = middle + 1;
        else
            return middle;
    }
    return -1;
}




int main(){
    int i=-2 , array[] = {0,1,2,3,6,7,8,9};
    for(;i<15;i++)
        cout << "searching : " << i <<  "\t\t position : " << binary_search_iterative(array , i , 0 , getArrayLen(array)) << endl;
    return 0;
}

결실

searching : -2       position : -1
searching : -1       position : -1
searching : 0        position : 0
searching : 1        position : 1
searching : 2        position : 2
searching : 3        position : 3
searching : 4        position : -1
searching : 5        position : -1
searching : 6        position : 4
searching : 7        position : 5
searching : 8        position : 6
searching : 9        position : 7
searching : 10       position : -1
searching : 11       position : -1
searching : 12       position : -1
searching : 13       position : -1
searching : 14       position : -1
Program ended with exit code: 0

우 리 는 2 를 실현 하 는 것 과 1 을 실현 하 는 결과 와 공간 복잡 도 는 같 고 공간 복잡 도 는 다르다 는 것 을 보 았 다.
시간 복잡 도
T(n)=T(2/n)+O(1) O(logN)
공간 복잡 도
O(1)
마지막.
위의 간단 한 설명 을 통 해 친구 들 이 그 원리 와 특성 을 이미 알 고 있다 고 믿는다.본인 의 능력 에 한계 가 있 습 니 다. 만약 잘못 을 발견 하거나 불합리 하 게 지적 을 환영 합 니 다.