二分查找
二分只能在有顺序的一组数据中使用,如果一组数据乱序,
可以使用结构体。
struct number{
int i; //第几个数
int j; //数值
}a[N];
{
bool cmp(number&a,number&b)
{
return a.j>b.j;
}
sort(a,a+N,cmp);
}
下面继续二分算法
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
//数组大小,由题进行赋值,+10可以防止数组越界
int a[N];
int main()
{
int m;
scanf("%d",&m);
for(int i=0;i<m;i++)scanf("%d",&a[i]);
int b; //需要判断的数字
scanf("%d",&b);
int left=0,right=m-1,mid;
//left为左边界,right为右边界,mid为每次中点
bool c=true; //判断数组中是否存在所判断的数
while(left<=right){
mid=(left+right)>>1; //取中点
if(a[mid]==b){
//中点为所判断的数时跳出循环,
c=false;
//数组中存在所给数时改变bool状态
break;
}
else if(a[mid]>b)right=mid-1;
else left=mid+1; //见下面
}
if(c)printf("-1\n");
else printf("%d\n",mid);
return 0;
}
对于二分,无非难搞懂其边界问题,会出现死循环,下面可以解决且好理解:
else if(a[mid]>b)right=mid-1;
//当中间值大于所给值时,将区间向左推
else left=mid+1;
//同理
下面为图解
如下:
1 2 3 4 5 6
查找 4
while第一次: left=0,right=5,mid=2,a[mid]=3<4=m
将区间向右推:
1 2 3 4 5 6
left=mid+1=3
left|-------------->4 5 6<-|right=5
----------------------------------------------
while第二次:left=3,right=5,mid=4,a[mid]=5>4=m
将区间向左推:
1 2 3 4 5 6
right=mid-1=3
3=left|-------------->4<---------|right
-------------------------------------------------
while第三次:left=3,right=3,mid=3,a[mid]=4==4=m
循环结束,查询三次!
如果一组数组中有重复元素,需要找出所以所有数据的下标范围
可以以mid为中心,向左右进行遍历
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int a[N];
int main()
{
int m,n;
scanf("%d %d",&m,&n);
for(int i=0;i<m;i++)scanf("%d",&a[i]);
while(n--){
int b;
scanf("%d",&b);
int left=0,right=m-1,t_l,t_r;
bool c=true;
while(left<=right){
int mid=(left+right)>>1;
if(a[mid]==b){
t_l=mid;
t_r=mid;
c=false;
break;
}else if(a[mid]>b)right=mid-1;
else left=mid+1;
}
while(1){
t_l--;
if(a[t_l]!=b)
break;
}
while(1){
t_r++;
if(a[t_r]!=b)
break;
}
if(c)printf("-1 -1\n");
else printf("%d %d\n",++t_l,--t_r);
}
return 0;
}