III.二分算法

目录

A.程序或算法的时间复杂度

B.二分查找 

C.求方程的根

D.寻找指定和的整数对

E.Aggressive cows 

---

A.程序或算法的时间复杂度

---

• 在无序数列中查找某个数(顺序查找) O(n)
• 平面上有n个点，要求出任意两点之间的距离 O(n2)
• 插入排序、选择排序、冒泡排序 O(n2)
• 快速排序 O( n*log(n))
• 二分查找O(log(n))

B.二分查找 

---

题目描述

A心里想一个1-1000之间的数，B来猜，可以问问题，A只能回答是或否。怎么猜才能问的问题次数最少？

题目解答

每次缩小猜测范围到上次的范围的一半，只需要10次

• 写一个函数BinarySeach，在包含size个元素的、从小到大排序的int数组a里查找元素p,如果找到，则返回元素下标，如果找不到，则返回-1。要求复杂度O(log(n))

int BinarySearch(int a[],int size,int p)
{
    int L = 0;//查找区间的左端点
    int R = size - 1;//查找区间的右端点
    while( L<=R )//如果查找区间不为空就继续查找
    {
        int mid = L + (R-L)/2;//取查找区间正中元素的下标
        if( p == a[mid] )
            return mid;
        else if( p > a[mid] )
            L = mid + 1;//设置新的查找区间的左端点
        else
            R = mid - 1;; //设置新的查找区间的右端点
    }
    return -1;
}//复杂度O(log(n))

•  写一个函数LowerBound，在包含size个元素的、从小到大排序的int数组a里查找比给定整数p小的，下标最大的元素。找到则返回其下标，找不到则返回-1

int LowerBound(int a[],int size,int p)//复杂度O(log(n))
{
    int L = 0;//查找区间的左端点
    int R = size - 1;//查找区间的右端点
    int lastPos = -1;//到目前为止找到的最优解
    while( L<=R )//如果查找区间不为空就继续查找
    {
        int mid = L + (R-L)/2;//取查找区间正中元素的下标
        if(a[mid]>=p)
            R = mid - 1;
        else
        {
            lastPos = mid;
            L = mid + 1;
        }
    }
    return lastPos;
}

 注意

        int mid = (L+R)/2; //取查找区间正中元素的下标

为了防止 (L+R)过大溢出:

        int mid = L+(R-L)/2;

C.求方程的根

题目描述

求下面方程的一个根：f(x) = x3-5x2+10x-80 = 0若求出的根是a，则要求 |f(a)| <= 10-6

题目解答

对f(x)求导，得f'(x)=3x2-10x+10。由一元二次方程求根公式知方程f'(x)= 0 无解，因此f'(x)恒大于0。故f(x)是单调递增的。易知 f(0) < 0且f(100)>0,所以区间[0,100]内必然有且只有一个根。由于f(x)在[0,100]内是单调的，所以可以用二分的办法在区间[0,100]中寻找根。

#include 
#include 
 
double EPS = 1e-6;
double f(double x)
{
    return x*x*x - 5*x*x +10*x - 80;
}
 
int main()
{
    double root, x1 = 0, x2 = 100;
    root = x1 + (x2-x1)/2;
    int triedTimes = 1;
    double y;
    y = f(root);
    while( fabs(y) > EPS)
    {
        if( y > 0 )
            x2 = root;
        else
            x1 = root;
        root = x1 + (x2 - x1)/2;
        y = f(root);
        triedTimes ++;
    }
    printf("%.8f\n",root);
    printf("%d",triedTimes);
    return 0;
}

D.寻找指定和的整数对

题目描述

输入n ( n<= 100,000)个整数，找出其中的两个数，它们之和等于整数m(假定肯定有解)。题中所有整数都能用 int 表示

解法一:

        用两重循环，枚举所有的取数方法，复杂度是O(n2)的。

for(int i = 0;i < n-1;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if( a[i]+b[j] == m)
                break;
        }
    }

 解法二：

• 将数组排序，复杂度是O(n×log(n))
• 对数组中的每个元素a[i],在数组中二分查找m-a[i]，看能否找到。复杂度log(n)，最坏要查找n-2次，所以查找这部分的复杂度也是O(n×log(n))

解法三：(x)

• 将数组排序，复杂度是O(n×log(n))
• 查找的时候，设置两个变量i和j,i初值是0,j初值是n-1.看a[i]+a[j],如果大于m，就让j减1，如果小于m,就让i加1，直至a[i]+a[j]=m。

#include 
#include 
 
int int_cmp(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;//升序排序
}
 
int main()
{
    int n;
    scanf("%d",&n);
    int a[100001];
    for(int i=0;i < n;i++)
    {
        scanf("%d",&a[i]);
    }
    qsort(a, n, sizeof(a[0]), int_cmp);
    int m;
    scanf("%d",&m);
    int i = 0, j = n-1;
    if( a[i] + a[j] > m)
        j--;
    else if( a[i] + a[j] < m)
        i++;
    else
        printf("%d + %d == %d",a[i],a[j],m);
    return 0;
}
 

E.Aggressive cows 

题目描述

农夫 John 建造了一座很长的畜栏，它包括N (2≤N≤100,000)个隔间，这些小隔间的位置为x0,...,xN-1 (0≤xi≤1,000,000,000,均为整数,各不相同).
John的C (2≤C≤N)头牛每头分到一个隔间。牛都希望互相离得远点省得互相打扰。怎样才能使任意两头牛之间的最小距离尽可能的大，这个最大的最小距离是多少呢？

解法一：

先得到排序后的隔间坐标 x0,...,xN-1
从1,000,000,000/C到1依次尝试这个 “最大的最近距离”D，找到的第一个可行的就是答案。
尝试方法：

1)    第1头牛放在x0
2)    若第k头牛放在xi ，则找到xi+1到xN-1中第一个位于[xi+D, 1,000,000,000]中的Xj ,第k+1头牛放在Xj。找不到这样的Xj,则 D=D-1,转 1)再试若所有牛都能放下，则D即答案

解法二：（x）

先得到排序后的隔间坐标 x0,...,xN-1
在[L,R]内用二分法尝试“最大最近距离”D = (L+R)/2 (L,R初值为[1,  1,000,000,000/C]
若D可行，则记住该D，然后在新[L,R]中继续尝试(L= D+1)
若D不可行，则在新[L,R]中继续尝试(R= D-1)

#include 
 
bool check(int mid,int a[],int n,int m)
{
	int cnt = 1;
	int cur = a[0];
	for(int i =1;i < n;i++)//从第二头牛开始放
    {
        if(a[i]-cur >= mid)
        {
			cnt++;//放下则数量加一
			cur = a[i];//如果放下，则将当前的牛栏作为初始继续往后找可以放的下的
		}
	}
	if(cnt>=m)//在给定的值下能够放下的牛的个数大于m，则说明给的值小了
		return true;
    else
	    return false;
}
 
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	int a[100000];
	for(int i =0;i < n;i++)
    {
		scanf("%d",&a[i]);
	}
	sort(a,a+n);
	int left = 0, right = a[n-1];//二分取值
	int mid = left + (right-left)/2;
	while(left<=right)
	{
		if( check(mid,a,n,m) )
            left = mid + 1;
		else
            right = mid - 1;
		mid = left + (right-left)/2;
	}
	printf("%d",right);
}