二分查找总结——左闭右开区间和左闭右闭区间(C++语言)

二分查找总结——左闭右开区间和左闭右闭区间(C++语言)二分查找:1.左闭右开区间,如有相同元素返回查找到的第一个元素。PS:主循环判断条件都是一样的(left<right),注意这里不能取等号!有相同元素时,如果要返回第一个查找到的元素,则区间包含相同元素时应该从右向左收缩,这时判断条件应该加上等号,并且此时找到的就是第一个元素的秩;如果要返回最后一个查找到的元素,则区间包含相同元素时应该从左向右收缩,这时判断条件没有等号,并且此时…

二分查找总结——左闭右开区间和左闭右闭区间(C++语言)"

二分查找:

1.左闭右开区间,如有相同元素返回查找到的第一个元素。

PS:主循环判断条件都是一样的(left < right),注意这里不能取等号!有相同元素时,如果要返回第一个查找到的元素,则区间包含相同元素时应该从右向左收缩,这时判断条件应该加上等号,并且此时找到的就是第一个元素的秩;如果要返回最后一个查找到的元素,则区间包含相同元素时应该从左向右收缩,这时判断条件没有等号,并且此时找到的是大于目标元素的第一个元素的秩,因此应该返回的目标元素的秩等于找到的秩减一。

#include <iostream>
#include <stdio.h>

using namespace std;

//左闭右开,相同元素返回第一个
int binSearch(int* A, int e, int left, int right)
{
	while (left < right)
	{
		int mid = left + ((right - left) >> 1);   //移位操作比除操作快
		(e <= A[mid]) ? right = mid : left = mid + 1; //从右向左收缩
	} 
	return left;    //找到的就是需要返回的
}

int main()
{
	int A[10] = { 0, 1, 2, 3, 3, 4, 5, 6, 6, 7 };
	int a = binSearch(A, 0, 0, 10);
	int b = binSearch(A, 1, 0, 10);
	int c = binSearch(A, 2, 0, 10);
	int d = binSearch(A, 3, 0, 10);
	int e = binSearch(A, 4, 0, 10);
	int f = binSearch(A, 5, 0, 10);
	int g = binSearch(A, 6, 0, 10);
	int h = binSearch(A, 7, 0, 10);

	printf("a=%d,b=%d,c=%d,d=%d,e=%d,f=%d,g=%d,h=%d\n", a, b, c, d, e, f, g, h);

	system("pause");
	return 0;
}

2.左闭右开区间,如有相同元素返回查找到的最后一个元素。

#include <iostream>
#include <stdio.h>

using namespace std;

//左闭右开,相同元素返回最后一个
int binSearch(int* A, int e, int left, int right)
{
	while (left < right)
	{
		int mid = left + ((right - left) >> 1);   //移位操作比除操作快
		(e < A[mid]) ? right = mid : left = mid + 1;  //从左向右收缩
	}
	return --left;      //真正返回的要减一
}

int main()
{
	int A[10] = { 0, 1, 2, 3, 3, 4, 5, 6, 6, 7 };
	int a = binSearch(A, 0, 0, 10);
	int b = binSearch(A, 1, 0, 10);
	int c = binSearch(A, 2, 0, 10);
	int d = binSearch(A, 3, 0, 10);
	int e = binSearch(A, 4, 0, 10);
	int f = binSearch(A, 5, 0, 10);
	int g = binSearch(A, 6, 0, 10);
	int h = binSearch(A, 7, 0, 10);

	printf("a=%d,b=%d,c=%d,d=%d,e=%d,f=%d,g=%d,h=%d\n", a, b, c, d, e, f, g, h);

	system("pause");
	return 0;
}

3.左闭右闭区间,如有相同元素返回查找到的第一个元素。

PS:左闭右闭区间,主循环的判断条件要加上等于号,即(left <= right),而right = mid -1;这里很好理解,在右开区间的时候,不用减1,因为最右边的我们取不到是开区间,而当右边是闭区间的时候,我们要减一,从而可以变成和右边开区间一样的效果。其他的返回第一个元素和返回最后一个元素同左闭右开区间。

#include <iostream>
#include <stdio.h>

using namespace std;

//左闭右闭,相同元素返回第一个
int binSearch(int* A, int e, int left, int right)
{
	while (left <= right)
	{
		int mid = left + ((right - left) >> 1);   //移位操作比除操作快
		(e <= A[mid]) ? right = mid - 1 : left = mid + 1; //从右向左收缩
	} 
	return left;    //找到的就是需要返回的
}

int main()
{
	int A[10] = { 0, 1, 2, 3, 3, 4, 5, 6, 6, 7 };
	int a = binSearch(A, 0, 0, 9);
	int b = binSearch(A, 1, 0, 9);
	int c = binSearch(A, 2, 0, 9);
	int d = binSearch(A, 3, 0, 9);
	int e = binSearch(A, 4, 0, 9);
	int f = binSearch(A, 5, 0, 9);
	int g = binSearch(A, 6, 0, 9);
	int h = binSearch(A, 7, 0, 9);

	printf("a=%d,b=%d,c=%d,d=%d,e=%d,f=%d,g=%d,h=%d\n", a, b, c, d, e, f, g, h);

	system("pause");
	return 0;
}

4.左闭右闭区间,如有相同元素返回查找到的最后一个元素。

#include <iostream>
#include <stdio.h>

using namespace std;

//左闭右闭,相同元素返回最后一个
int binSearch(int* A, int e, int left, int right)
{
	while (left <= right)
	{
		int mid = left + ((right - left) >> 1);   //移位操作比除操作快
		(e < A[mid]) ? right = mid - 1 : left = mid + 1;  //从左向右收缩
	}
	return --left;      //真正返回的要减一
}

int main()
{
	int A[10] = { 0, 1, 2, 3, 3, 4, 5, 6, 6, 7 };
	int a = binSearch(A, 0, 0, 9);
	int b = binSearch(A, 1, 0, 9);
	int c = binSearch(A, 2, 0, 9);
	int d = binSearch(A, 3, 0, 9);
	int e = binSearch(A, 4, 0, 9);
	int f = binSearch(A, 5, 0, 9);
	int g = binSearch(A, 6, 0, 9);
	int h = binSearch(A, 7, 0, 9);

	printf("a=%d,b=%d,c=%d,d=%d,e=%d,f=%d,g=%d,h=%d\n", a, b, c, d, e, f, g, h);

	system("pause");
	return 0;
}

 

今天的文章二分查找总结——左闭右开区间和左闭右闭区间(C++语言)分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/28107.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注