主要是二分法的时间复杂度的计算方法。

作业里能通过的代码如下：

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
 1 Position BinarySearch(List L,ElementType X){
 2     int mid=0,l=1,r=(*L).Last;
 3     mid=(l+r)/2;
 4         while(l<=r){
 5         if(X==(*L).Data[mid]){
 6             return mid;
 7         }
 8         else if(X<(*L).Data[mid]){
 9             r=mid-1;
10             mid=(l+r)/2;
11         }
12         else if(X>(*L).Data[mid]){
13             l=mid+1;
14             mid=(l+r)/2;
15         }
16     }
17     return NotFound;
18 }

二分法一次去掉数组中的一半元素，以8个数为例：

9*(1/2)=4

9*(1/2^2)=2

9*(1/2^3)=1

共需要k次操作：

n*(1/2^k)=1

n=2^k

k=log n

即T(n)=O(log n).

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄