Q3) int search_idx func 만들기
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <list>
#include <ctime>
using namespace std;
int search_idx(const int a[], int n, int key, int idx[]){
int i, cnt=0;
for(i=0;i<n;i++){
if(a[i]==key)
idx[cnt++]=i; // 검색 성공하면 idx 배열에 요소 배열의 위치 값을 넣음
}
return cnt;
}
int main(){
int i, ncnt, nfnd;
int kcnt;//key와 일치하는 요소의 개수
int *x; // 데이터를 저장하는 배열
int *idx; // key와 일치하는 요소의 인덱스 저장하는 배열
puts("요소 개수 : ");
cin>>ncnt;
x = (int *)calloc(ncnt, sizeof(int));
idx = (int *)calloc(ncnt, sizeof(int));
for(i=0;i<ncnt;i++){ // 요소 입력
cout << "x["<<i<<"] : ";
cin>>x[i];
}
cout <<"찾는 값 : ";
cin>>nfnd;
kcnt=search_idx(x,ncnt,nfnd,idx); // 배열 x에서 값이 nfnd인 요소를 선형 검색
if(kcnt==-1)
cout<<"일치 값 없음"<<endl;
else{
cout <<"일치하는 값은 "<<kcnt<<"개 이다."<<endl;
for(i=0;i<kcnt;i++){
cout <<"x["<<idx[i]<<"]";
cout<<" ";
}
puts("");
}
free(x);
free(idx);
return 0;
}
Q5) 맨 앞 요소를 찾는 int search_idx2 func 만들기 // Error :: 수정 필요
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <list>
#include <ctime>
using namespace std;
int search_idx2(const int a[], int n, int key){
int f_idx=0;
int l_idx=0;
int c_idx;
do{
c_idx = (f_idx+l_idx)/2;
if(a[c_idx]==key){ // 검색 성공
while(c_idx>f_idx && a[c_idx-1]==key){
// 중간 idx가 검색 범위 첫 인덱스보다 크고 (AND) 검색 범위를 앞쪽 반 줄인것에서 검색 성공 한 경우
c_idx--;
}
return c_idx;
}else if(a[c_idx]<key)
f_idx=c_idx+1;//검색 버위 뒤쪽 반으로 줄임
else
l_idx = c_idx-1;//검색 범위 앞쪽 반으로 줄임
}while(f_idx<=l_idx);
return -1;// 검색 실패
}
int main(){
int i, ncnt, nfnd, idx;
int *x; // 데이터를 저장하는 배열
puts("요소 개수 : ");
cin>>ncnt;
x = (int *)calloc(ncnt, sizeof(int));
puts("x[0] : ");
cin>>x[0];
puts("오름차순으로 입력하라 ");
for(i=1;i<ncnt;i++){ // 요소 입력
do{
cout << "x["<<i<<"] : ";
cin>>x[i];
}while(x[i]<x[i-1]); // 바로 앞의 값보다 작으면 다시 입력
}
cout <<"찾는 값 : ";
cin>>nfnd;
idx=search_idx2(x,ncnt,nfnd); // 배열 x에서 값이 nfnd인 요소를 선형 검색
if(idx==-1)
cout<<"검색 실패"<<endl;
else
cout <<nfnd<<"는 x["<<idx<<"]"<<"에 있다.";
free(x);
return 0;
}
