Dichotomy: exact search

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; Int a [] = 9,1,2,2,3,5 {1}; 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}Copy the code

Binary upper limit lookup:

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; Int a [] = 9,2,2,2,5,6 {2}; 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}Copy the code

Binary lower limit lookup:

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; Int a [] = 9,2,2,2,3,6 {1}; 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}Copy the code