C++ 알고리즘 - 검색

선형검색(linear search)

1. while문 사용

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <list>
#include <ctime>
using namespace std;
// 요소 개수가 n인 배열a에서 key와 일치하는 요소를 선형 검색
int search(const int a[], int n, int key){
    int i=0;// 배열 순서
    while(1){
        if(i==n)
            return -1;
        if(a[i]==key)
            return i;
        i++;
    }
}
int main(){
    int i, ncnt, nfnd, idx;
    int *x;
    puts("선형 검색");
    cout <<"요소 개수 : ";
    cin>>ncnt;
    
    //요소가 ncnt개인 배열 x 생성
    x = (int*)calloc(ncnt, sizeof(int));
    for(i=0;i<ncnt;i++){
        cout <<"x["<<i<<"] : ";
        cin>>x[i];
    }
    cout<<"검색값 : ";
    cin>>nfnd;
    
    idx=search(x,ncnt,nfnd);
    if(idx==-1)
        puts("검색 실패");
    else
        cout <<nfnd<<"은(는) x["<<idx<<"]에 있습니다.";
    free(x);
    return 0;
}

 

2. for문 사용

    for(int i=0;i<n;i++){
        if(a[i]==key)
            return i; // 검색 성공
        return -1; // 검색 실패
    }

 

for(int i=0;a[i]!='\0';i++) // 배열 끝까지 돌기

---

무한루프 구현

1. while(1){}

2. for(;;){}

3. do{.  }while(1)

 

 

보초법(sentinal method)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <list>
#include <ctime>
using namespace std;
// 요소 개수가 n인 배열a에서 key와 일치하는 요소를 선형 검색
int search(int a[], int n, int key){
    int i=0;// 배열 순서
    a[n]=key; //보초 추가
    while(1){
        if(a[i]==key)// 원하는 값을 찾은 경우
            break;
        i++;
    }
    return i==n ? -1 : i; //i==n 이면 찾은 값이 보초값이다 그래서 -1 return
    
}
int main(){
    int i, ncnt, nfnd, idx;
    int *x;
    puts("선형 검색");
    cout <<"요소 개수 : ";
    cin>>ncnt;
    
    //요소가 ncnt+1 개인 배열 x 생성
    x = (int*)calloc(ncnt+1, sizeof(int));
    for(i=0;i<ncnt;i++){// ****** 주의 ******* 값을 읽어들인 것은 ncnt개
        cout <<"x["<<i<<"] : ";
        cin>>x[i];
    }
    cout<<"검색값 : ";
    cin>>nfnd;
    
    idx=search(x,ncnt,nfnd);
    if(idx==-1)
        puts("검색 실패");
    else
        cout <<nfnd<<"은(는) x["<<idx<<"]에 있습니다.";
    free(x);
    return 0;
}

 

 

---

 

이진 검색(Binary Search)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <list>
#include <ctime>
using namespace std;
int binary_search(const int a[], int n, int key){
    int f_idx=0; // 검색 범위 맨 처음
    int l_idx=n-1; // 검색 범위 맨 끝
    int c_idx; // 검색 범위 중간
    do{
        c_idx=(f_idx+l_idx)/2;
        if(a[c_idx]==key)//찾는 값과 같으면 :: 검색 성공
            return c_idx;
        else if(a[c_idx]<key)
            f_idx=c_idx+1;
        else if(a[c_idx]>key)
            l_idx=c_idx-1;
    }while(f_idx<=l_idx);
    return -1; // 검색 실패
}
int main(){
    int i, ncnt, nfnd, idx;
    int *x;
    puts("이진 검색");
    cout <<"요소 개수 : ";
    cin>>ncnt;
    
    x = (int*)calloc(ncnt, sizeof(int));
    cout <<"오름차순으로 입력하시오"<<endl;
    cout <<"x[0] : ";
    cin>>x[0];
    for(i=1;i<ncnt;i++){
        do{
            cout <<"x["<<i<<"] : ";
            cin>>x[i];
        }while(x[i]<x[i-1]); // 바로 앞의 값보다 작으면 다시 입력
    }
    cout<<"검색값 : ";
    cin>>nfnd;
    
    idx=binary_search(x,ncnt,nfnd);
    if(idx==-1)
        puts("검색 실패");
    else
        cout <<nfnd<<"은(는) x["<<idx<<"]에 있습니다."<<endl;
    free(x);
    return 0;
}