이분 검색법(귀속과 순환 실현)
정렬수 그룹과 숫자 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2분 검색의 순환 버전과 귀속 버전이분 검색은 질서정연한 표에서 원소가 존재하는지 찾는 것이다. 시간의 복잡도는 대수 단계이고 많은 문제에서 변체가 있다. 이분 검색의 귀속 버전 실현과 비귀속 버전을 복습해 보자. 코드 및 테스트 함수:...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.