二分【1】二分查找框架 查找指定元素

目录

二分查找 基本思想

 几种情况汇总

一。严格递增序列

1.查找本身

2.查找第一个大于等于自己的 

3.查找第一个大于自己的

4.严格递减序列

二。有重复元素

1.取其中第一个出现的

2.取其中最后一个出现的

---

二分查找 基本思想

 几种情况汇总

一。严格递增序列

1.查找本身

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<=right){mid=left+(right-left)/2;if(num[mid]>x) right=mid-1;if(num[mid]<x) left=mid+1;if(num[mid]==x){for(int i=mid;i>0;i--)if(num[i]==x&&num[i-1]!=x) return i;}}return -1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

2.查找第一个大于等于自己的 

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<right){mid=left+(right-left)/2;if(num[mid]>x||num[mid]==x) right=mid;if(num[mid]<x) left=mid+1;}if(num[left]>=x) return left;else return left+1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

3.查找第一个大于自己的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<right){mid=left+(right-left)/2;if(num[mid]>x) right=mid;if(num[mid]<x||num[mid]==x) left=mid+1;}if(num[left]>x) return left;else return left+1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

4.严格递减序列

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<=right){mid=left+(right-left)/2;if(num[mid]>x) left=mid+1;if(num[mid]<x) right=mid-1;if(num[mid]==x) return mid;}return -1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

二。有重复元素

1.取其中第一个出现的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<=right){mid=left+(right-left)/2;if(num[mid]>x) right=mid-1;if(num[mid]<x) left=mid+1;if(num[mid]==x){for(int i=mid;i>0;i--)if(num[i]==x&&num[i-1]!=x) return i;return 0;}}return -1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}

2.取其中最后一个出现的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{while(left<=right){mid=left+(right-left)/2;if(num[mid]>x) right=mid-1;if(num[mid]<x) left=mid+1;if(num[mid]==x){for(int i=mid;i>0;i--)if(num[i]==x&&num[i-1]!=x) return i;return 0;}}return -1;
}
int main()
{scanf("%d %d",&n,&x);for(int i=0;i<n;i++) scanf("%d",&num[i]);printf("%d",bis(num,0,n-1,x));}