二分搜索(续)

　　　　　　上一节末尾提到了一个问题，在顺序数组中找到t值第一次出现的位置。

其实这也是一种二分搜索的变形。

思路如下：我仍然使用l和u作为数组的边界值，t就包含在l和u指示的数组范围中。但不变关系式变为x[l]<t<=x[u]和l<u,此时，我们假设n>=0,x[-1]<t以及 x[n]>=t(程序中并没有这两个元素)。二分搜索的代码如下

 1 int binarySearch(int a[],int n,int t)//n为a数组的长度,t为寻找的元素
 2 {
 3     
 4     if(n<=0)
 5         {
 6             return -1;
 7         }
 8     
 9     int low=-1;
10     int high=n;
11     int middle;
12     while(low+1!=high)
13     {
14         middle=(low+high)/2;
15         if(a[middle]<t)
16             {
17                 low=middle;
18             }
19             else  //此时的条件改为a[middle]>=t而不是原先的程序需要比较两次
20             {
21                     high=middle;
22             }
23                 
24     }
25     if(high>=n||a[high]!=t)
26         {
27             return -1;
28         }
29         else
30             {
31                 return high;
32             }
33 }

此程序的好处是在while循环中只需要将数组a中的值与t值比较一次，而不是前文中的两次。有时候看似很细微的差别就可以对性能造成举足轻重的影响。