이분 검색법(귀속과 순환 실현)

2374 단어 이분 검색귀속
질문:
정렬수 그룹과 숫자 k를 정하고 첫 번째 k의 위치와 마지막 k의 위치를 찾으십시오
해결:
주어진 수조는 작은 그룹에서 큰 그룹으로 정렬되기 때문에 이분 검색법에 따라 찾을 수 있다. 다음은 각각 귀속과 순환 두 가지 방법으로 논술한다.
// 
int GetFirstK(int* data, int length, int k, int start, int end)
{
	if (start > end)
		return -1;
	int middleindex = (start + end) / 2;
	int middledata = data[middleindex];
	if (middledata>k)
	{
		end = middleindex - 1;
	}
	else if (middledata<k)
	{
		start = middleindex + 1;
	}
	else
	{
		if (middleindex==0||(middleindex>0&&data[middleindex-1]!=k))// k, , k , k middledata
		{
			return middleindex;
		}
		else
		{
			
			end = middleindex - 1;
		}
	}
	return  GetFirstK(data, length, k,start, end);
}
// 
int GetFirstK(int* data, int length, int k)
{
	int start = 0;
	int end = length - 1;
	while (start<=end)
	{

		int middleindex = (start + end) / 2;
		int middledata = data[middleindex];
		if (middledata<k)
		{
			start = middleindex + 1;
		}
		else if (middleindex>k)
		{
			end = middleindex - 1;
		}
		else
		{
			if (middleindex==0||(middleindex>0&&data[middleindex-1]!=k))
			{
				return middleindex;
			}
			else
			{
				end = middleindex - 1;
			}
		}
	}
	
	return -1;

}
// 
int GetLastK(int* data, int length, int k, int start, int end)
{
	if (start>end)
	{
		return -1;
	}
	int middleindex = (start + end) >> 1;
	int middledata = data[middleindex];
	if (middledata<k)
	{
		start = middleindex + 1;
	}
	else if (middledata>k)
	{
		end = middleindex - 1;
	}
	else
	{
		if (middleindex==length-1||(middleindex<length-1&&data[middleindex+1]!=k))
		{
			return middleindex;
		}
		else
		{
			start = middleindex + 1;
		}
	}
	return GetLastK(data, length, k, start, end);
}
// 
int GetLastK(int* data, int length, int k)
{
	int start = 0;
	int end = length - 1;
	while (start<=end)
	{
		int middleindex = (start + end) >> 1;
		int middledata = data[middleindex];
		if (middledata>k)
		{
			end = middleindex - 1;
		}
		else if (middledata<k)
		{
			start = middleindex + 1;
		}
		else
		{
			if (middleindex==length-1||(middleindex<length-1&&data[middleindex+1]!=k))
			{
				return middleindex;
			}
			else
			{
				start = middleindex + 1;
			}
		}
	}
	return -1;
}

좋은 웹페이지 즐겨찾기