关于 二分 的总结：
问题1：
在一个给定范围的序列里，猜数字这个游戏可是非常的经典。
显然 每次选择当前范围的中间数去猜，就能尽可能快的逼近这个正确的数字！！！
在这个简单有趣的游戏背后，是一个算法中经典的问题：如何在一个依然有序的序列中找到这个给定的数?
解法一：直接扫描法 从到开始扫描，但是显然它的时间复杂度 O（n）。虽然说，查询次数不多时，还是可以的，但是100000个数需要查询，那么就不太好了！！！！
解法二：二分查找 大前提：有序
struct status
{
int num;
bool tag;
};
status binarySearch(int *s, int len, int n)//如果找到n，则返回其下标
{
status mysta;
assert(s != nullptr);
int left = 0, right = len - 1;
while (left <= right)
{
//int mid = (left + right) / 2;
int mid=left+(right-left)/2;//防止int 溢出
if (s[mid] == n)
{
mysta.tag = true;
mysta.num = mid;
return mysta;
}
else if (s[mid] < n)
{
left = mid + 1;
}
else right = mid - 1;
}
mysta.tag = false;
mysta.num = -1;
return mysta;
}
int main()
{
int A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20 };
int num;
while (scanf("%d", &num))
{
cout << "请输入一个要查询的数：" << endl;
int n; cin >> n;
int arraylen = sizeof(A) / sizeof(A[0]);
status s = binarySearch(A, arraylen, n);
if (s.tag)
{
cout << "它的下标是：" << s.num << endl;
}
else cout << "数组中不存在这个数！！！！" << endl;
}
return 0;
}
运行结果：
问题二：
如果递增序列A的元素有重复，那么如何对给定的x值，求出序列中第一个大于等于x的元素位置L以及第一个大于x的元素位置R，这样x在这个序列中的存在区间就是左闭右开区间[L,R).?
首先：如何求序列中的第一个大于等于x的元素位置？
int lower_bound(int *s, int left, int right, int n)//n是要查询的数。返回第一个不小于n的元素的位置
{//我这个程序的 数组 left和right是数组的合法下标【0，length-1】
assert(s != nullptr);
while (left < right)
{
int mid = left + (right - left) / 2;
if (s[mid] >= n)//中间数不小于n 说明往左区间【left,mid】找
{
right = mid;
}
else left = mid + 1;//中间数小于n 说明往右区间【mid+1，right】找
}
if (s[left] >= n)
{
return left;
}
else return left + 1;//如果我输入的数 比数组的数都大，则返回的位置应该是length
}
int main()
{
int Array[10] = { 1, 2, 2, 3, 3, 4, 6, 6, 6, 10 };//数组为递增数组
int n;
cout << "请输入要查询的数n=：";
while (scanf("%d", &n)&&n!=0)
{
cout << "第一个不小于"<<n<<"的下标为：" << lower_bound(Array, 0, 9, n) << endl;
cout << "请输入要查询的数：";
}
return 0;
}
接下来：求序列中的第一个大于等于x的元素位置
int upper_bound(int *s, int left, int right, int n)//n是要查询的数。返回第一个大于n的元素的位置
{//我这个程序的 数组 left和right是数组的合法下标【0，length-1】
assert(s != nullptr);
while (left < right)
{
int mid = left + (right - left) / 2;
if (s[mid] > n)
{
right = mid;
}
else
{
left = mid + 1;
}
}
if (n >= s[left])
{
return left + 1;
}
else return left;
}
int main()
{
int Array[10] = { 1, 2, 2, 3, 3, 4, 6, 6, 6, 10 };//数组为递增数组
int n;
cout << "请输入要查询的数n=：";
while (scanf("%d", &n) && n != 0)
{
cout << "第一个大于" << n << "的下标为：" << upper_bound(Array, 0, 9, n) << endl;
cout << "请输入要查询的数：";
}
return 0;
}
运行截图：
最后汇总：得到一个数的范围：
int lower_bound(int *s, int left, int right, int n)//n是要查询的数。返回第一个大于等于n的元素的位置
{//我这个程序的 数组 left和right是数组的合法下标【0，length-1】
assert(s != nullptr);
while (left < right)
{
int mid = left + (right - left) / 2;
if (s[mid] >= n)//中间数不小于n 说明往左区间【left,mid】找
{
right = mid;
}
else left = mid + 1;//中间数小于n 说明往右区间【mid+1，right】找
}
if (s[left] >= n)
{
return left;
}
else return left + 1;
}
int upper_bound(int *s, int left, int right, int n)//n是要查询的数。返回第一个大于n的元素的位置
{//我这个程序的 数组 left和right是数组的合法下标【0，length-1】
assert(s != nullptr);
while (left < right)
{
int mid = left + (right - left) / 2;
if (s[mid] > n)
{
right = mid;
}
else
{
left = mid + 1;
}
}
if (n >= s[left])
{
return left + 1;
}
else return left;
}
int main()
{
int Array[10] = { 1, 2, 2, 3, 3, 4, 6, 6, 6, 10 };//数组为递增数组
int n;
cout << "请输入要查询的数n=：";
while (scanf("%d", &n) && n != 0)
{
cout << "这个数的范围下标为[" << lower_bound(Array, 0, 9, n) << ",";
cout << upper_bound(Array, 0, 9, n) <<")"<< endl;
cout << "请输入要查询的数：";
}
return 0;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
以上是左闭右闭的情况，现在是左开右闭的
//这两个函数方法上是 左开右闭的写法 （left,right】，而且left比最小取值小1
int lower_bound2(int A[], int left, int right, int n)//求序列中第一个大于等于n的位置
{
assert(A != nullptr);
int mid;
while (left + 1 < right)
{
mid = left + (right - left) / 2;
if (A[mid] < n)
{
left = mid;
}
else
{
right = mid;
}
}
return A[right] < n ? right + 1 : right;
}
int upper_bound2(int A[], int left, int right, int n)//求序列中第一个大于n的元素的位置
{
assert(A != nullptr);
int mid;
while (left + 1 < right)
{
mid = left + (right - left) / 2;
if (A[mid] > n)
{
right = mid;
}
else
{
left = mid;
}
}
return A[right] < n ? right + 1 : right;
}
int main()
{
int Array[10] = { 1, 2, 2, 3, 3, 4, 6, 6, 6, 10 };//数组为递增数组
int n;
cout << "请输入要查询的数n=：";
while (scanf("%d", &n) && n != 0)
{
cout << "这个数的范围下标为[" << lower_bound2(Array, -1, 9, n) << ",";
cout << upper_bound2(Array, -1, 9, n) <<")"<< endl;
cout << "请输入要查询的数：";
}
return 0;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
二分法的拓展：求根号2的近似值（以精确到10-5次方）。
const double eps = 1e-5;//控制误差
inline double CalPow(double n)//求n平方
{
return n*n;
}
int main()
{
double left = 1, right = 2, mid;
while (left + eps < right)
{
mid = left + (right - left) / 2;
if (CalPow(mid)>2)
{
right = mid;
}
else left = mid;
}
printf("%.8f\n", mid);
return 0;
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<