ACM-二分/三分查找

本文最后更新于：December 3, 2021 pm

实现二分和三分查找。

目录

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//#define _CRT_SECURE_NO_DEPRECATE
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<functional>
#include<numeric>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define IOS ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
using namespace std;
const int INF=0x3f3f3f3f;
const long long maxn=1e6+5;
#define PI acos(-1)
int find(int a[],int len,int m)                 //len为数组的长度  m为被查找的数
{
    int left = 0, right = len - 1;
    while (left <= right)
    {
        int k=left+(right-left)/2;
        if (m == a[k])                  //即 m就为中间值
            return k;
        else if (m > a[k])              //即m在中间到最后这一段里面
            left = k + 1;               //所以就让left从中间的下一个开始 重复二分查找
        else
            right = k - 1;              //即 m在开始到中间这一段里面
    }
    return -1;                          //如没有上述三种情况 则就是没有找到 即没有m元素
}

void solve(){
	int t[100];
	int n,m;
	cout<<"请输入总个数和要查找的数："<<endl;
	cin>>n>>m;
	cout<<"请输入数："<<endl;
	for(int i=0;i<n;++i) cin>>t[i];
	sort(t,t+n);
	int f=find(t,n,m);
	if(f==-1) cout<<"NO!"<<endl;
	else cout<<"OK!"<<endl;

}
int main(){
	IOS;
	solve();
	return 0;
}

三分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//#define _CRT_SECURE_NO_DEPRECATE
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<functional>
#include<numeric>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define IOS ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
using namespace std;
const int INF=0x3f3f3f3f;
const long long maxn=1e6+5;
#define PI acos(-1)
int find3(int *a,int l,int r,int key){
	int flag;
	if(l>r) flag=-1;
	else{
		int mid1=(r-l)/3+l; //自行带入数据比较好理解
		int mid2=r-(r-l)/3;
		if(key==a[mid1]) flag=mid1;
		else if(key==a[mid2]) flag=mid2;
		else if(key<a[mid1]) flag=find3(a,l,mid1-1,key);
		else if(key>a[mid2]) flag=find3(a,mid2+1,r,key);
		else flag=find3(a,mid1+1,mid2-1,key);
	}
	return flag;
}
void solve(){
	int t[100];
	int n,m;
	cout<<"请输入总个数和要查找的数："<<endl;
	cin>>n>>m;
	cout<<"请输入数："<<endl;
	for(int i=1;i<=n;++i) cin>>t[i];
	sort(t+1,t+n+1);
	int f=find3(t,1,n,m);
	if(f==-1) cout<<"NO!"<<endl;
	else cout<<"OK!"<<endl;

}
int main(){
	IOS;
	solve();
	return 0;
}
ACM

本文作者: 墨水记忆
本文链接: https://tothefor.com/DragonOne/1274539156.html
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！