首页 > 代码库 > 二分查找 模板

二分查找 模板

2024-07-17 05:39:30   220人阅读

 1 int bsearch(int l, int h, int k)//二分查找函数 2 { 3     int i, mid; 4      5     while(l<=h){ 6         mid = l+(h-l)/2; 7         if(X[mid]>k) 8             h = mid-1; 9         else if(X[mid]<k)10             l = mid+1;11         else 12             break;13     }14     return mid;15 }

 

 1 int max_bsearch(int l, int h, int k)//求上界 2 { 3     int i, mid, ans = -1; 4  5     while(l<=h){ 6         mid = l+(h-l)/2; 7         if(X[mid]>=k){ 8             h = mid-1; 9             ans =X[mid];10         }11         else12             l = mid+1;13     }14     return ans;15 }

 

 1 int min_bsearch(int l, int h,int k)//求下界 2 { 3     int i, mid, ans = -1; 4  5     while(l<=h){ 6         mid = l+(h-l)/2; 7         if(X[mid]<=k){ 8             l = mid+1; 9             ans = X[mid];10         }11         else12             h = mid-1;13     }14     return ans;15 }
 1 void Quick_sort(int l, int h)//复习一下快排 2 { 3     int i = l, j = h; 4     int v = X[l]; 5  6     if(l>=h) 7         return ; 8     while(i<j){ 9         while(i<j && X[j]>=v)j--;10         X[i] = X[j];11         while(i<j && X[i]<=v)i++;12         X[j] = X[i];13     }14     X[i] = v;15     Quick_sort(l,i-1);16     Quick_sort(i+1,h);17 }

 

附上一道练习题

代码在这

  1 #include <iostream>  2 #include <cstdio>  3 #include <algorithm>  4 #include <cstring>  5 #define ll long long  6   7 using namespace std;  8   9 int X[1000003]; 10  11 void Quick_sort(int l, int h)//复习一下快排 12 { 13     int i = l, j = h; 14     int v = X[l]; 15  16     if(l>=h) 17         return ; 18     while(i<j){ 19         while(i<j && X[j]>=v)j--; 20         X[i] = X[j]; 21         while(i<j && X[i]<=v)i++; 22         X[j] = X[i]; 23     } 24     X[i] = v; 25     Quick_sort(l,i-1); 26     Quick_sort(i+1,h); 27 } 28  29 int max_bsearch(int l, int h, int k)//求上界 30 { 31     int i, mid, ans = -1; 32  33     while(l<=h){ 34         mid = l+(h-l)/2; 35         if(X[mid]>=k){ 36             h = mid-1; 37             ans =X[mid]; 38         } 39         else 40             l = mid+1; 41     } 42     return ans; 43 } 44  45 int bsearch(int l, int h, int k)//二分查找函数 46 { 47     int i, mid; 48      49     while(l<=h){ 50         mid = l+(h-l)/2; 51         if(X[mid]>k) 52             h = mid-1; 53         else if(X[mid]<k) 54             l = mid+1; 55         else  56             break; 57     } 58     return mid; 59 } 60  61 int min_bsearch(int l, int h,int k)//求下界 62 { 63     int i, mid, ans = -1; 64  65     while(l<=h){ 66         mid = l+(h-l)/2; 67         if(X[mid]<=k){ 68             l = mid+1; 69             ans = X[mid]; 70         } 71         else 72             h = mid-1; 73     } 74     return ans; 75 } 76  77 int main() 78 { 79     int n, m, i, j, k, a, b; 80  81     while(scanf("%d %d",&n,&m)==2){ 82         for(i=0;i<n;i++) 83             scanf("%d",X+i); 84         Quick_sort(0,n-1); 85         for(i=0;i<m;i++) 86         { 87             scanf("%d",&k); 88             a = min_bsearch(0,n-1,k); 89             b = max_bsearch(0,n-1,k); 90             if(a == -1)// 1 91                 printf("%d\n",b); 92             else if(b == -1)// 2 93                 printf("%d\n",a); 94             else if(a==b) 95                 printf("%d\n",a); 96             else if(k-a == b-k) 97                 printf("%d %d\n",a,b); 98             else if(k-a>b-k) 99                 printf("%d\n",b);100             else101                 printf("%d\n",a);102         }103         //1和2两条语句是非常重要的不然的话可以测试一下 n=1 ,m=5,X[0]=1,k=0这组数据。104         printf("\n");105     }106     return 0;107 }
Here

 

当然你可以调用C中的<stdlib.h>中的qsort或C++中的<algorithm>sort。二分查找就用C中的<stdlib.h>中的bsearch。


联系
我们