学步园

之前写的二分算法的模板  现在略作更新

点击打开链接

标准的二分算法的形式是：

template<class Typep>
int BinarySearch(Type a[],const Type& x,int n) // 总共n个值 数组从0开始 
{
     int left=0;
     int right=n-1;
     while(left<=right){
          int middle=(left+right)/2;
          if(a[middle]==x)return middle;  //返回查找到的位置 
          if(a[middle]>x)right=middle-1;
          else left=middle+1;                  
     }    
      return -1;  //没有找到 
     
}

但是往往题中给出的不是数组中的数，需要在数组中找到比查找的值刚刚大的数，那么我们就需要改动return -1;的值 那么改到什么最好呢？

下面我们就来证明

a[1]   a[2]    a[3]

10    20      30

a[1]=10;  a[2]=20;  a[3]=30;

现在我们要查找15；

(1)查找的范围值[1,2]  ------这里指的是数组的位置

left=1,right=2;

进入while 循环中 

middle=1;

num>a[middle]=a[1];

left=middle+1;

result:      left=2;  midddle=1,right=1;

跳出循环

(2)  查找的范围是[1,3]

left=1,right=3;

进入while循环

middle=2;

num<a[middle]=a[2]

right=middle-1=1;

middle=2,left=1;

进行第二次循环

middle=1;

a[middle]<num

left=middle+1=2;

left=2; middle=1,right=1;

因为是二分查找的情况 所有的情况都会演变成[1,2]和[1,,3]的情况

然后如果要找刚刚大于一点的 选择left的

若是要找刚刚小于一点的 选择right

----  上面的这两句话就是更改最后一个return 的值 是他返回left和right

然后要注意的是  可以再所给集合中多添加两个边界值 使之 将所有的范围固定 这样就可以求解了

举个例子

要对下面的8个数进行2分查找

2,55,6,7,35,34,88,56

我们加上两个边界值 -1000和1000 控制范围

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[10]={-1000,1000,2,55,6,7,35,34,88,56};
int BinarySearch(int n,int num){
     int left=0;
     int right=n-1;
     int middle;
     while(left<=right){
      //printf("left=%d right=%d\n",left,right);
        middle=(left+right)/2;
        if(a[middle]==num)return middle;
        if(a[middle]>num)right=middle-1;
        else left=middle+1;                   
     }            
     return left;   //刚刚大于一点的
}

int main()
{
   sort(a,a+10);
   int n=10;         //8个查找数加上两个范围
   int num;
   for(int i=0;i<10;i++)
      printf("%d ",a[i]);
   printf("\n"); 
   while(scanf("%d",&num)!=EOF){
        int pos=BinarySearch(n,num);
        printf("pos=%d a[%d]=%d\n",pos,pos,a[pos]);
   }  
}