二分查找:
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