C++ 이분검색/ 버블정렬/ 알고리즘 / 코딩

 

 

 

 

 

 

2분검색 의 기준은 정렬이다!

 

정렬이 되어 있지 않은 상황에서는 이분 검색을 할수 없다.

 

 

말이 들어갈 위치를 1차원의 직선 좌표로 생각 한다면,

 

제일 처음 과 끝을 2로 나눈 수로 체크 하며 말을 넣어 본다.

 

1~10까지의 수평면 상에서 중간 값인 5를 가지고 말을 넣는다고 가정할때 ,

 

원하는 말을 다 넣을수 없으면 , 제일 처음의 수 1과 5를 더한후 2로 나눈 값으로 다시 찾는다.

 

이과정을 반복하며 , 말의 최대 거리를 출력한다.

 

아래는 소스 파일을 첨부 합니다. 

 

 

 

 

마구간.cpp

다운로드

 

 

 

 

 

 

 

#include <stdio.h>

#include <iostream>

using namespace std;





int main() 

{

 int array[10] = {1,2,6,4,9,3,5,7,14,15};

 int pos[100] = { 0, };

 int horse = 3;

 int mid = (array[0] + array[4]) / 2;

 int pre_mid=0;

 int left = array[0];

 int left_index = 0;

 int horse_count = 1;

 int temp;

 int distance = 0;



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

 {

 int temp = 0;

 for (int k = 0; k < 10; k++) 

 {

 if (array[i] < array[k]) 

 {

 int temp = array[i];

 array[i] = array[k];

 array[k] = temp;

 }

 }

 }   //정렬 구현 부



 while (true) 

 { 

 for (int i = left_index; i < 10; i++) {

 if (array[i] >= (left + mid)) {

 left = array[i];

 left_index = i;

 horse_count++;

 break;

 }

 }

 if (horse_count == horse) 

 {

 if(distance < mid )

 distance = mid;

 }



 if (mid == pre_mid) break; // 직전의 미드 값과 나눈후의 미드 값이 같아 진다면 와일문 나감.//



 if (array[9] < (left + mid)){



 pre_mid = mid;     //2등분으로 나누다 보면 언젠가는 같아질 경우 나가야 한다//

 mid = (mid + 1) / 2;

 left_index = 0;

 left = array[0];

 horse_count = 0;

 }

 }



 cout << "max: " << distance << endl;

 system("pause");

}