二分法及其拓展

二分法及拓展

①确定一个数（最多一个）的位置

#include<iostream>
using namespace std;
int binarySearch(int A[], int left, int right, int x)
{
	int mid;
	while (left <= right)
	{
		//mid = (left + right) / 2;
		mid = left + (right - left) / 2;
		if (A[mid] == x)
			return mid;
		else if (A[mid] > x)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
}
int main()
{
	int A[10] = { 1,3,4,6,7,8,10,11,12,15 };
	cout << binarySearch(A, 0, 9, 6);
}

②确定一个数（可能多个）的范围

#include<iostream>
using namespace std;
int lower_bound(int A[], int left, int right, int x)
{
	int mid;
	while (left < right)
	{
		mid = (right + left) / 2;
		if (A[mid] >= x)
			right = mid;
		else
			left = mid + 1;
	}
	return left;
}
int upper_bound(int A[], int left, int right, int x)
{
	int mid;
	while (left < right)
	{
		mid = (left + right) / 2;
		if (A[mid] > x)
			right = mid;
		else
			left = mid + 1;
	}
	return left;
}
int main()
{
	int A[10] = { 1,3,4,6,7,7,10,11,12,15 };
	cout << "x∈[" << lower_bound(A, 0, 10, 7) << "," << upper_bound(A, 0, 10, 7) << ")";
}

③求根号2的大小

#include<iostream>
using namespace std;
const double eps = 1e-5;
double fuc(double x)
{
	return x * x;
}
double calsqrt()
{
	double left = 1, right = 2, mid;
	while (right - left > eps)
	{
		mid = (left + right) / 2;
		if (fuc(mid) > 2)
			right = mid;
		else
			left = mid;
	}
	return mid;
}
int main()
{
	cout << calsqrt();
}

④求解函数fuc()=x*x-2在递增区间[1,2]上的零根

#include<iostream>
using namespace std;
const double eps = 1e-5;
double fuc(double x)
{
	return x * x - 2;
}
double solve(double L,double R)
{
	double left = L, right = R, mid;
	while (right - left > eps)
	{
		mid = (left + right) / 2;
		if (fuc(mid) > 0)
			right = mid;
		else
			left = mid;
	}
	return mid;
}
int main()
{
	cout << solve(1,2);
}

⑤木棒切割：长度相等的一些木棒切割成至少7根长度相等的木棒，求最大切割长度

#include<iostream>
using namespace std;
int cmp(int A[], int N, int length)
{
	int sum = 0;
	for (int i = 0; i < N; i++)
		sum += A[i] / length;
	return sum;
}
int stick(int A[], int N, int k)
{
	int left = 0, right = 0;
	for (int i = 0; i < N; i++)
		if (A[i] > right)
			right = A[i];
	int mid;
	while (left + 1 < right)
	{
		mid = (left + right) / 2;
		if (cmp(A, N, mid) < k)
			right = mid;
		else
			left = mid;
	}
	return left;
}
int main()
{
	int A[3] = { 10,24,15 };
	int k = 7;
	cout << stick(A, 3, 7) << endl;
}