이진탐색+Recrusion (되부름 알고리즘)

이진탐색+Recrusion (되부름 알고리즘)

 

 

#include <iostream>

#include <iomanip>

using namespace std;

bool bi_Iterative(int list[], int end, int target, int & locn);

bool bi_Recursive();

const int SIZE=100;

int main(void)

{

int list[SIZE];

int srchArgu;

int foundLocn;

//배열 채우기

for(int i=0; i < SIZE; i++)

{

list[i]=2*i;

}

for(int i=0; i < SIZE; i++)

{

if(i%10==0)

{

cout<<endl;

}

else

{

cout<<setw(4)<<list[i];

}

}

cout<<endl<<"원하는 숫자입력:";

cin>>srchArgu;

bool res=bi_Recursive(list, SIZE-1,srchArgu,foundLocn);

if(res ==true)

{

cout<<"데이터 찾음"<<list[foundLocn]<<endl;

}

else

{

cout<<srchArgu<<"데이터를 못찾음"<< endl;

}

}

//

//bool bi_Iterative(int list[], int end, int target, int & locn)

//{

// int first=0, mid, last=end;

//

//

// while(first<=last)

// {

// mid=(first+last)/2;

//

// if(target>list[mid])

// {

// first=mid+1;

// }

// else if(target<list[mid])

// {

// last=mid-1;

// }

// else

// {

// break;

// }

// }

//

// locn=mid;

//

// return (target == list[mid]);

//

//}

bool bi_Recursive(int list[], int end, int target, int & locn)

{

int first=0, mid, last=end;

mid=(first+last)/2;

if(first<=last)

{

if(target == list[mid])

{

return (target == list[mid]);

}

else if(target>list[mid])

{

first=mid+1;

bi_Recursive(list,mid,first,locn);

}

else if(target<list[mid])

{

last=mid-1;

bi_Recursive(list,last,mid,locn);

}

}

locn=mid;

}