二分查找和二分答案

二分查找

1.解釋:

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。它充分利用了元素間的次序關系，采用分治政策，可在最壞的情況下用O(log n)完成搜尋任務。

2.基本思想：（以升序為例）

将n個元素分n成個數大緻相同的兩半，取a[ n/2 ]與欲查找的x作比較，如果x=a[ n/2 ]則找到x,算法終止;如果x<a[ n/2 ],則我們隻要在數組a的左半部分繼續搜尋x;如果x>a[ n/2 ],則我們隻要在數組a的右半部繼續搜尋x。

3.優缺點:

優點:查找速度快。

缺點:待查表為有序表。

4.時間複雜度:

O(log n)

5.示例:

P2249查找

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,a[1000005],b[100005],l,r,mid,cnt,x;
int main()
{
	scanf("%lld%lld",&n,&m);//n:數字個數,m:詢問次數
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);//a[i]待查詢數字
	}
	for(int i=0;i<m;i++)
	{
		scanf("%lld",&x);//查找x在序列中第一次出現的編号，沒有則輸出-1
		//開始二分
		l=1;//左端
		r=n;//右端
		while(l<r)
		{
			mid=l+(r-l)/2;//中點
			if(a[mid]>=x)
			{
				r=mid;
			}
			else 
			{
				l=mid+1;
			}
		}
		if(a[l]==x)
		{
			b[cnt++]=l;
		}
		else
		{
			b[cnt++]=-1;
		}
	}
	for(int i=0;i<m;i++)
	{
		printf("%lld ",b[i]);
	}
	printf("\n");
	return 0;
}
           

二分答案

1.非正式的解釋: （後續會更新）

在題目的答案範圍内，利用二分假設答案，對每一個假設的答案，用一個自定義的check函數判斷該假設的答案是否為該題的答案，如果不是繼續二分下一個。

2.适用:

1.求最大最小/最小的最大

2.求最靠近一個值的值

3.示例:

P2678跳石頭

//L,N,M,分别表示起點到終點的距離,起點和終點之間的岩石數,以及組委會至多移走的岩石數。
#include<bits/stdc++.h>
using namespace std;
long long l,m,n,a[50005],t;
bool check(long long x)  //check函數:由題目要求自定義
{
	long long ll=0,cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]-ll<x)
			cnt++;
		else
			ll=a[i];
	}
	if(cnt<=m)
		return 1;
	else
		return 0;
}
int main()
{
	scanf("%lld%lld%lld",&l,&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);  //a[i]表示第i塊岩石與起點的距離
		//t=max(t,a[i]);
	}
	long long ans=0,low=0,high=l,mid;
	//long long ans=0,low=1,high=t,mid;兩個都行 
	while(low<=high)
	{
		mid=(low+high)/2;
		if(check(mid))
		{
			ans=mid;
			low=mid+1;
		}
		else
		{
			high=mid-1;
		}
	}
	printf("%lld\n",ans);
	return 0;
}
           

4.推薦模闆(來自y總)

整數二分算法模闆

//方法1:
// 區間[l, r]被劃分成[l, mid]和[mid + 1, r]時使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判斷mid是否滿足性質
        else l = mid + 1;
    }
    return l;
}

//方法2；
// 區間[l, r]被劃分成[l, mid - 1]和[mid, r]時使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

           

浮點數二分算法模闆

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取決于題目對精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}
           

如有錯誤,歡迎指出。