C/C++ 이진탐색/ 바이너리서치/이분검색/

 

 

 

 

 

 

 

 

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

#include <vector>



using namespace std;





int show() {

 int serch;



 cout << "찾을 수를 입력 하세요 " << endl;

 cin >> serch;

 cout << serch << "값을 찾겠습니다." << endl;



 return serch;

}



void bubbleSort(vector <int> *res) {

 //sort

 for (int i = 0; i < (*res).size(); i++)

 {

 int temp = 0;

 for (int k = 0; k < (*res).size(); k++)

 {

 if ((*res)[i] < (*res)[k])

 {

 temp = (*res)[i];

 (*res)[i] = (*res)[k];

 (*res)[k] = temp;

 }

 }

 }

}



int binarySearch(vector <int> *res)

{

 //sort

 int findNum = show(); //사용자가 입력한 값

 int start_Index = 0;

 int end_Index = (*res).size()-1;

 int middle_Index = (*res).size() / 2;

 int baseNum = 0; // 배열에 기준값

 int pre_end = 0;

 int pre_start = 0;



 bubbleSort(res); 



 while(true){



 middle_Index = start_Index + (end_Index - start_Index) / 2;

 pre_end = end_Index;

 pre_start = start_Index;



 baseNum = (*res)[middle_Index];



 if (baseNum == findNum) break;



 if (baseNum < findNum) { // 오른쪽에서 찾아라 

 start_Index = middle_Index;

 //end_Index = (*res).size() - 1;

 end_Index = pre_end;

 }

 else //왼쪽에서 찾아라 

 {

 //start_Index = 0;

 start_Index = pre_start;

 end_Index = middle_Index;

 }



 }



 return middle_Index; // 해당값을 찾은 위치(인덱스값)

}









int main() 

{ 

 vector <int> *res=new vector <int> (); // 지역변수 인 vector를 사용하기위해선 포인터화 후 메개변수로 넘겨줘야 함.

 int num;

 int index = 0;



 cout << "데이터를 몇개 입력하시겠습니까?";

 cin >> num;



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

 {

 int nVal=0;

 cin >> nVal;

 (*res).insert(res->begin() + i, nVal);

 }





 index=binarySearch(res);

 cout << index << "위치에서 찾았습니다." << endl;





 system("pause");

 return 0;

}