// binarysearch.cpp : O(log2N)의 탐색 평균속도를 내는 2진탐색 샘플
// http://krkim.net

#include "stdafx.h"
#include "windows.h"

struct MYDATA{
	int pos;
	int style;
};

int binarysearch(int *arraylist,int arraysize,int findvalue);
int binarysearchprev(MYDATA *arraylist,int arraysize,int findvalue,int findstyle);

int _tmain(int argc, _TCHAR* argv[])
{
	int arraylist[]={10,12,13,15,18,27,39,100,101,113,215,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
	int arraylist2[]={-1,-1,-1};

	MYDATA mylist[] = { {10,1},{15,1},{17,1},{110,1},{120,2},{129,1},{2100,1},{-1,1},{-1,1},{-1,1}};

	//binarysearch(arraylist,ARRAYSIZE(arraylist),15);
	binarysearchprev(mylist,ARRAYSIZE(mylist),2000,2);
	return 0;
}

int binarysearch(int *arraylist,int arraysize,int findvalue)
{
	int lo = 0;
	int hi = arraysize - 1;
	int cp;
	int loop = 0;
	int dummyvalue = -1;
//	while(hi > 0 && arraylist[hi] == -1) hi--;

	for(;;){
		loop++;
		cp = (lo + hi) / 2;
		
		if(findvalue == arraylist[cp]){
			break;
		}
		if(lo >= hi)
			break;

		if(arraylist[cp] == dummyvalue)//뒷부분이 dummy로 채워져 있음
			hi = cp - 1;
		else if(findvalue > arraylist[cp]){
			lo = cp + 1;
			//같은값이 없으면 항상 크거나 작은 값 둘중 어느하나가 불규칙하게 탐색된다.
			//이유는,배열의 데이타 갯수 여부의 홀짝에 따라 중간값이 달라지기 때문이다.
			//따라서,같은값이 없을때 작은값을 구하기 위해 비교한다.
			//같은값만 찾으려면 아래는 필요없음.또는 데이타의 끝에 dummy 값을 만나도 멈춤
			//같은값이 없으면 작은값중 최대값으로 찾고 뒷부분의 더미바이트를 만나면 멈춘다.
			if(findvalue < arraylist[lo] || arraylist[lo] == dummyvalue){
				break;
			}
		}
		else
			hi = cp - 1;
	}
	char msg[300];
	sprintf(msg,"loop[%d] findvalue = %d => array[%d] = %d\r\n",loop,findvalue,cp,arraylist[cp]);
	OutputDebugStr(msg);

	return 0;
}


//findvalue보다 pos가 작거나같고 style이 findstyle 과 다른 항목 찾기
int binarysearchprev(MYDATA *arraylist,int arraysize,int findvalue,int findstyle)
{
	int lo = 0;
	int hi = arraysize - 1;
	int cp;
	int loop = 0;
	int dummyvalue = -1;
	//	while(hi > 0 && arraylist[hi] == -1) hi--;

	for(;;){
		loop++;
		cp = (lo + hi) / 2;
		if(findvalue == arraylist[cp].pos)
			break;
		if(lo >= hi)
			break;
		if(arraylist[cp].pos == dummyvalue)//뒷부분이 dummy로 채워져 있음
			hi = cp - 1;
		else if(findvalue > arraylist[cp].pos){
			lo = cp + 1;
			if(findvalue < arraylist[lo].pos || arraylist[lo].pos == dummyvalue){
				break;
			}
		}
		else
			hi = cp - 1;
	}
	int loop2 = 0;
	int findpos = -1;
	for(int pos = cp; findpos == -1 && pos >= 0 ; pos--){
		loop2++;
		if(arraylist[pos].pos <= findvalue && arraylist[pos].style != findstyle)
			findpos = pos;
	}
	char msg[300];
	if(findpos != -1){
		cp = findpos;
		sprintf(msg,"loop[%d] loop2[%d] findvalue = (%d,%d) => array[%d] = (%d,%d)\r\n",
			loop,loop2,findvalue,findstyle,cp,arraylist[cp].pos,arraylist[cp].style);
		OutputDebugStr(msg);
	}
	else{
		sprintf(msg,"loop[%d] loop2[%d] findvalue = (%d,%d) => not found in this list\r\n",
			loop,loop2,findvalue,findstyle);
		OutputDebugStr(msg);
	}

	return 0;
}
