2점짜리 케이스.

54588 단어 학습 노트
#include 
#include 

//  , , -1
int binary_search_org(int* data, int iBegin, int iEnd, int iTarget)
{
     
	while (iBegin <= iEnd)
	{
     
		int mid = iBegin + (iEnd - iBegin) / 2;
		auto iCurrentVal = data[mid];
		if (iCurrentVal == iTarget)
		{
     
			return mid;
		}
		else if(iCurrentVal > iTarget)
		{
     
			// 1 2 3 4 5 6       1
			iEnd = mid - 1;
		}
		else
		{
     
			iBegin = mid + 1;
		}
	}
	return -1;
}
void test_binary_search_org()
{
     
	int data[] = {
      1,2,3,4,5,6 };
	assert(binary_search_org(data, 0, _countof(data) - 1, 1) == 0);
	assert(binary_search_org(data, 0, _countof(data) - 1, 6) == 5);
	assert(binary_search_org(data, 0, _countof(data) - 1, -1) == -1);
	assert(binary_search_org(data, 0, _countof(data) - 1, 7) == -1);

	assert(binary_search_org(data, 0, 0, 1) == 0);
	assert(binary_search_org(data, 0, 0, 2) == -1);
}
int binary_search_first_big(int* data, int iBegin, int iEnd, int iTarget)
{
     
	int left = iBegin;
	int right = iEnd;
	while (left <= right) {
     
		int mid = left + (right - left) / 2;
		int iCurrentVal = data[mid];
		if (iCurrentVal > iTarget) {
     
			// 1 2 3 4 5 --->2
			right = mid - 1;// , 3   2, ,left = 1 + 1  2, 
		}
		else {
     
			left = mid + 1;//  
		}
	}
	return (left == iEnd + 1) ? -1 : left;
}
void test_binary_search_first_big()
{
     
	int data[] = {
      1,2,3,4,5,6 };
	assert(binary_search_first_big(data, 0, _countof(data) - 1, 1) == 1);
	assert(binary_search_first_big(data, 0, _countof(data) - 1, 2) == 2);
	assert(binary_search_first_big(data, 0, _countof(data) - 1, 6) == -1);
	assert(binary_search_first_big(data, 0, _countof(data) - 1, -1) == 0);
	assert(binary_search_first_big(data, 0, _countof(data) - 1, 7) == -1);

	assert(binary_search_first_big(data, 0, 0, 1) == -1);
	assert(binary_search_first_big(data, 0, 0, 2) == -1);
}

int binary_search_first_equalbig(int* data, int iBegin, int iEnd, int iTarget)
{
     
	int left = iBegin;
	int right = iEnd;
	while (left <= right) {
     
		int mid = left + (right - left) / 2;
		int iCurrentVal = data[mid];
		if (iCurrentVal >= iTarget) {
     
			// 1 2 3 4 5 --->2
			right = mid - 1;// , 3   2, ,left = 1 + 1  2, 
		}
		else {
     
			left = mid + 1;//  
		}
	}
	return (left == iEnd + 1) ? -1 : left;
}
void test_binary_search_first_equalbig()
{
     
	int data[] = {
      1,2,4,5,6,10 };
	assert(binary_search_first_equalbig(data, 0, _countof(data) - 1, 1) == 0);
	assert(binary_search_first_equalbig(data, 0, _countof(data) - 1, 2) == 1);
	assert(binary_search_first_equalbig(data, 0, _countof(data) - 1, 6) == 4);
	assert(binary_search_first_equalbig(data, 0, _countof(data) - 1, -1) == 0);
	assert(binary_search_first_equalbig(data, 0, _countof(data) - 1, 7) == 5);
	assert(binary_search_first_equalbig(data, 0, _countof(data) - 1, 10) == 5);
	assert(binary_search_first_equalbig(data, 0, _countof(data) - 1, 11) == -1);

	assert(binary_search_first_equalbig(data, 0, 0, 1) == 0);
	assert(binary_search_first_equalbig(data, 0, 0, 2) == -1);
}

int binary_search_last_equal(int* data, int iBegin, int iEnd, int iTarget)
{
     
	int left = iBegin;
	int right = iEnd;
	while (left <= right) {
     
		int mid = left + (right - left) / 2;
		int iCurrentVal = data[mid];
		if (iCurrentVal > iTarget) {
     
			// 3 3 3 4   --> 3
			//   
			//     |
			//     right  
			right = mid - 1;//
		}
		else{
     
			left = mid + 1;//  
		}
	}
	//  first_big
	//  

	if (left == iEnd + 1) {
     
		if (data[left - 1] == iTarget) return left - 1;
	}
	else if(left == 0)
	{
     
		return -1;
	}
	else
	{
     
		if (data[left - 1] == iTarget) return left - 1;
	}
	return -1;
}
void test_binary_search_last_equal()
{
     
	int data[] = {
      1,2,4,5,5,5,5,6,6,10 };
	assert(binary_search_last_equal(data, 0, _countof(data) - 1, 1) == 0);
	assert(binary_search_last_equal(data, 0, _countof(data) - 1, 2) == 1);
	assert(binary_search_last_equal(data, 0, _countof(data) - 1, 5) == 6);
	assert(binary_search_last_equal(data, 0, _countof(data) - 1, 6) == 8);
	assert(binary_search_last_equal(data, 0, _countof(data) - 1, 7) == -1);
	assert(binary_search_last_equal(data, 0, _countof(data) - 1, 10) == 9);
	assert(binary_search_last_equal(data, 0, _countof(data) - 1, 11) == -1);

	assert(binary_search_last_equal(data, 0, 0, 1) == 0);
	assert(binary_search_last_equal(data, 0, 0, 2) == -1);
}

int binary_search_first_little(int* data, int iBegin, int iEnd, int iTarget)
{
     
	int left = iBegin;
	int right = iEnd;
	while (left <= right) {
     
		int mid = left + (right - left) / 2;
		int iCurrentVal = data[mid];
		if (iCurrentVal >= iTarget) {
     
			// 3 3 3 4   --> 3
			//   
			//     |
			//     right  
			right = mid - 1;//
		}
		else {
     
			left = mid + 1;//  
		}
	}
	//  first_equal_big
	//  

	if (left == iEnd + 1) {
     
		return left - 1;
	}
	else if (left == 0)
	{
     
		return -1;
	}
	else
	{
     
		return left - 1;
	}
	return -1;
}
void test_binary_search_first_little()
{
     
	int data[] = {
      1,2,4,5,5,5,5,6,6,10 };
	assert(binary_search_first_little(data, 0, _countof(data) - 1, 1) == -1);
	assert(binary_search_first_little(data, 0, _countof(data) - 1, 2) == 0);
	assert(binary_search_first_little(data, 0, _countof(data) - 1, 5) == 2);
	assert(binary_search_first_little(data, 0, _countof(data) - 1, 6) == 6);
	assert(binary_search_first_little(data, 0, _countof(data) - 1, 7) == 8);
	assert(binary_search_first_little(data, 0, _countof(data) - 1, 10) == 8);
	assert(binary_search_first_little(data, 0, _countof(data) - 1, 11) == 9);

	assert(binary_search_first_little(data, 0, 0, 1) == -1);
	assert(binary_search_first_little(data, 0, 0, 2) == 0);
}
int main()
{
     
	test_binary_search_first_little();
	return 0;
}

좋은 웹페이지 즐겨찾기