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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
STL 학습노트(6) 함수 객체모방 함수는 모두pass-by-value이다 함수 대상은 값에 따라 전달되고 값에 따라 되돌아오기 때문에 함수 대상은 가능한 한 작아야 한다(대상 복사 비용이 크다) 함수 f와 대상 x, x 대상에서 f를 호출하면:...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.