在已经有序的数组 d 里面 , 找到一个大小为 num 的数字 , 数组的长度是 len

1 int erfen(int num,int len)  //  在 已经确定的 数列里面 2 { 3     int left,right,mid;   //    找到 要么可以替换的 数字要么 向后推一位  4     left=1; 5     right=len; 6     mid=(left+right)/2; 7     while(left<=right) 8     { 9         if(d[mid]
     
      num)12             right=mid-1;13         else14             return mid;15         mid=(left+right)/2;16     }17     return left;18 }

这个是自己写的函数 , 感觉自己写的不如 stl 函数库中的 , 下面附上 , stl 函数中的二分查找的各种函数 . STL中关于二分查找的函数有三个lower_bound 、upper_bound 、binary_search 。这三个函数都运用于有序区间（当然这也是运用二分查找的前提）。

迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器不仅仅是指针，因此你不能认为他们一定具有地址值。例如，一个数组索引，也可以认为是一种迭代器。

STL中关于二分查找的函数有三个lower_bound 、upper_bound 、binary_search 。这三个函数都运用于有序区间（当然这也是运用二分查找的前提）。

其中如果寻找的value存在，那么lower_bound返回一个迭代器指向其中第一个这个元素。upper_bound返回一个迭代器指向其中最后一个这个元素的下一个位置（明确点说就是返回在不破坏顺序的情况下，可插入value的最后一个位置）。如果寻找的value不存在，那么lower_bound和upper_bound都返回“假设这样的元素存在时应该出现的位置”。要指出的是lower_bound和upper_bound在源码中只是变换了if—else语句判定条件的顺序，就产生了最终迭代器位置不同的效果。

binary_search试图在已排序的[first,last)中寻找元素value，若存在就返回true，若不存在则返回false。返回单纯的布尔值也许不能满足需求，而lower_bound、upper_bound能提供额外的信息。事实上由源码可知binary_search便是利用lower_bound求出元素应该出现的位置，然后再比较该位置的值与value的值。该函数有两个版本一个是operator< ，另外一个是利用仿函数comp进行比较。

先上lower_bound 它既可以返回第一个比查找数字大的值 , 也可以返回第一个该数字的位置 , 下面先附上返回位置的代码

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                13 #include
                 
                  14 using namespace std; // 二分查找 , 效率挺高的 , 下面是 stl 中 二分查找的 代码 15 int main()16 {17 int a[10];18 for(int i=0;i<10;i++) 19 a[i]=2*i;20 int n;21 sort(a,a+10);22 int location;23 while(scanf("%d",&n))24 {25 location=lower_bound(a,a+10,n)-a; // 如果 location 是 指针的话 返回的 就是 值 , 如果不是指针的话 返回的就是 位置 26 printf("%d\n",location);27 }28 return 0;29 }

返回值的情况

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  using namespace std; int main(){ int a[10]; for(int i=0;i<10;i++) a[i]=2*i; int n; sort(a,a+10); int *location; while(scanf("%d",&n)) { location=lower_bound(a,a+10,n); // 缺点是 , 如果查找的数字 过大的话 返回的是 那个比较大的数字 . printf("%d\n",*location); } return 0;}

下面附上 upper_bound 的应用方式 (upper_bound返回一个迭代器指向其中最后一个这个元素的下一个位置（明确点说就是返回在不破坏顺序的情况下，可插入value的最后一个位置) 剩下的都一样

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  using namespace std;int main(){ int a[10]; for(int i=0;i<10;i++) a[i]=5; int n; sort(a,a+10); int location; while(scanf("%d",&n)) { location=upper_bound(a,a+10,n)-a; // 缺点是 , 如果查找的数字 过大的话 返回的是 那个比较大的数字 . printf("%d\n",location); } return 0;}