二分查找模版
二分：精确查找
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int main() 7 { 8 int target,i,j,mid,r,l; 9 int a[]={1,1,2,2,3,5}; 10 cout<<a[5]<<endl; 11 target=3; 12 l=0;r=6; 13 while(r>=l) 14 { 15 mid=(r+l)>>1; 16 if(a[mid]==target) 17 break; 18 else if(a[mid]<target) 19 l=mid+1; 20 else 21 r=mid-1; 22 } 23 printf("%d\n",mid); 24 }
二分上限查找：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int main() 7 { 8 int target,i,j,mid,r,l; 9 int a[]={2,2,2,2,5,6}; 10 //cout<<a[5]<<endl; 11 target=2; 12 l=0;r=6; 13 mid=(l+r)>>1; 14 while(r>l) 15 { 16 if(a[mid]>target) 17 r=mid; 18 else 19 l=mid+1; 20 mid=(l+r)>>1; 21 } 22 printf("%d\n",mid); 23 }
二分下限查找：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int main() 7 { 8 int target,i,j,mid,r,l; 9 int a[]={1,2,2,2,3,6}; 10 //cout<<a[5]<<endl; 11 target=2; 12 l=0;r=6; 13 mid=(l+r+1)>>1; 14 while(r>l) 15 { 16 if(a[mid]<target) 17 l=mid; 18 else 19 r=mid-1; 20 mid=(l+r+1)>>1; 21 } 22 printf("%d\n",mid); 23 }