二分查找和multiset用法

逃离我推掉我的手 2022-07-15 10:39 196阅读 0赞

二分查找和multiset用法

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    struct Rule//定义排序规则：按个位数从小到大排序 
    {
    	bool operator()(const int & a1,const int & a2){
    		return a1%10<a2%10;
    	}
    };
    
    void Print(int a[],int size){//输出数据 
    	for(int i=0;i<size;i++){
    		cout<<a[i]<<" ";
    	}
    	cout<<endl;
    }
    
    int main(){
    	int a[]={12,45,3,98,21,7};
    	sort(a,a+6);//从小到大排序 
    	Print(a,6);
    	cout<<"result:"<<binary_search(a,a+6,12)<<endl;
    	cout<<"result:"<<binary_search(a,a+6,77)<<endl;
    	
    	sort(a,a+6,Rule());
    	Print(a,6);
    	cout<<"result:"<<binary_search(a,a+6,7)<<endl;
    	cout<<"result:"<<binary_search(a,a+6,8,Rule())<<endl;
    	
    	system("pause");
    	return 0;
    }

![20161113202146480][]

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    struct Student{//定义学生结构体 
    	char name[20];
    	int id;
    	double gpa;
    }; 
    
    Student students[]={
       {"Jack",112,3.4},{"Mary",102,3.8},{"Mary",117,3.9},{"Ala",333,3.5},{"lily",101,4.0}};
    
    struct StudentRule1{//姓名从小到大 
    	bool operator()(const Student &s1,const Student &s2){
    		if(strcmp(s1.name,s2.name)<0)
    			return true;
    		return false;
    	}
    };
    
    struct StudentRule2{//学号从小到大 
    	bool operator()(const Student & s1,const Student & s2){
    		return s1.id<s2.id;
    	}
    };
    
    struct StudentRule3{//绩点从大到小 
    	bool operator()(const Student & s1,const Student &s2){
    		return s1.gpa>s2.gpa;
    	}
    };
    
    void PrintStudents(Student s[],int size){//输出学生信息 
    	for(int i=0;i<size;i++){
    		cout<<"("<<s[i].name<<","<<s[i].id<<","<<s[i].gpa<<")";
    	}
    	cout<<endl;
    }
    
    int main(){
    	Student s;
    	strcpy(s.name,"Mary");//复制 
    	s.id=117;
    	s.gpa=0;
    	int n=sizeof(students)/sizeof(Student);
    	sort(students,students+n,StudentRule1());
    	PrintStudents(students,n);
    	cout<<binary_search(students,students+n,s,StudentRule1())<<endl;
    	
    	strcpy(s.name,"Bob");
    	cout<<binary_search(students,students+n,s,StudentRule1())<<endl;
    	
    	sort(students,students+n,StudentRule2());
    	PrintStudents(students,n);
    	cout<<binary_search(students,students+n,s,StudentRule2())<<endl;
    	
    	system("pause");
    	return 0;
    }

![20161113202403279][]

上界、下界查找（二分查找）

#include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    struct Rule//按个位从小到大排序 
    {
    	bool operator()(const int &a1,const int &a2){
    		return a1%10<a2%10;
    	}
    };
    
    void Print(int a[],int size){//输出数组中的数据 
    	for(int i=0;i<size;i++){
    		cout<<a[i]<<" ";
    	}
    	cout<<endl;
    }
    
    #define NUM 7
    
    int main(){
    	int a[NUM]={12,5,3,5,98,21,7};
    	sort(a,a+NUM);//从小到大排序 
    	Print(a,NUM);//从小到大输出 
    	
    	int *p=lower_bound(a,a+NUM,5);
    	cout<<*p<<","<<p-a<<endl;//查找出5的值和位置（下界） 
    	
    	p=upper_bound(a,a+NUM,5);
    	cout<<*p<<","<<p-a<<endl;//查找出5的值和位置（上界） 
    	
    	cout<<*upper_bound(a,a+NUM,13)<<endl;//查找13的值（上界） 
    	
    	sort(a,a+NUM,Rule());//按个位从小到大排序 
    	Print(a,NUM);//输出数据 
    	cout<<*lower_bound(a,a+NUM,16,Rule())<<endl;//查找排序后16的上界值 
    	cout<<lower_bound(a,a+NUM,25,Rule())-a<<endl;//查找25的下界位置 
    	cout<<upper_bound(a,a+NUM,18,Rule())-a<<endl;//查找18的下界位置 
    	
    	if(upper_bound(a,a+NUM,18,Rule())==a+NUM)
    		cout<<"not found"<<endl;
    	cout<<*upper_bound(a,a+NUM,5,Rule())<<endl;
    	cout<<*upper_bound(a,a+NUM,4,Rule())<<endl;
    	
    	system("pause");
    	return 0;
    }

![20161113202642086][]

平衡二叉树（插入、删除、查找）multiset

#include<iostream>
    #include<cstring>
    #include<set>//使用multiset和set的头文件
    using namespace std;
    
    int main(){
    	multiset<int> st;
    	int a[10]={1,14,12,13,7,13,21,19,8,8};
    	for(int i=0;i<10;i++)
    		st.insert(a[i]);
    	multiset<int>::iterator i;
    	for(i=st.begin();i!=st.end();i++)
    		cout<<*i<<" ";
    	cout<<endl;
    	
    	i=st.find(22);
    	if(i==st.end())
    		cout<<"not found"<<endl;
    	st.insert(22);
    	i=st.find(22);
    	if(i==st.end())
    		cout<<"not found"<<endl;
    	else
    		cout<<"found:"<<*i<<endl;
    	
    	i=st.lower_bound(13);
    	cout<<*i<<endl;
    	i=st.upper_bound(8);
    	cout<<*i<<endl;
    	st.erase(i);
    	
    	for(i=st.begin();i!=st.end();++i){
    		cout<<*i<<" ";
    	}
    	system("pause");
    	return 0;
    }

![20161113202945328][]

[20161113202146480]: /images/20220715/022d51c27d1e4eb482c57e540d2ec9a8.png
[20161113202403279]: /images/20220715/63982862d30d42ccae29571f446fcc4e.png
[20161113202642086]: /images/20220715/34f85aa2049b49378f93d2bb37a5488e.png
[20161113202945328]: /images/20220715/64ed598d209c4aefbb250f5e291a1bf7.png