考虑问题 1 ：已知不重复且已经按从小到大排好的 m 个整数的数组 A[1..m] （为简单起见。还设 m=2 k ， k 是一个确定的非负整数）。对于给定的整数 c ，要求寻找一个下标 i ，使得 A[i]=c ；若找不到，则返回一个 0 。
问题 1 的一个简单的算法是：从头到尾扫描数组 A 。照此，或者扫到 A 的第 i 个分量，经检测满足 A[i]=c ；或者扫到 A 的最后一个分量，经检测仍不满足 A[i]=c 。我们用一个函数 Search 来表达这个算法：
Function Search (c:integer):integer;
Var J:integer;
Begin
J:=1; { 初始化 }
{ 在还没有到达 A 的最后一个分量且等于 c 的分量还没有找到时，
查找下一个分量并且进行检测 }
While (A[i]<c)and(j<m) do
j:=j+1;
If A[j]=c then search:=j { 在数组 A 中找到等于 c 的分量，且此分量的下标为 j}
else Search:=0; { 在数组中找不到等于 c 的分量 }
End;
容易看出，在最坏的情况下，这个算法要检测 A 的所有 m 个分量才能判断在 A 中找不到等于 c 的分量。
解决问题 1 的另一个算法利用到已知条件中 A 已排好序的性质。它首先拿 A 的中间分量 A[m/2] 与 c 比较，如果 A[m/2]=c 则解已找到。如果 A[m/2]>c ，则 c 只可能在 A[1],A[2],..,A[m/2-1] 之中，因而下一步只要在 A[1], A[2], .. ， A[m/2-1] 中继续查找；如果 A[m/2]<c ，则 c 只可能在 A[m/2+1],A[m/2+2],..,A[m] 之中，因而下一步只要在 A[m/2+1],A[m/2+2],..,A[m] 中继续查找。不管哪一种情形，都把下一步需要继续查找的范围缩小了一半。再拿这一半的子数组的中间分量与 c 比较，重复上述步骤。照此重复下去，总有一个时候，或者找到一个 i 使得 A[i]=c ，或者子数组为空（即子数组下界大于上界）。前一种情况找到了等于 c 的分量，后一种情况则找不到。
这个新算法因为有反复把供查找的数组分成两半，然后在其中一半继续查找的特征，我们称为二分查找算法。它可以用函数 B_Search 来表达：
Function B_Search ( c: integer):integer;
Var
L,U,I : integer; {U和L分别是要查找的数组的下标的上界和下界}
Found: boolean;
Begin
L:=1; U:=m; {初始化数组下标的上下界}
Found:=false; {当前要查找的范围是A[L]..A[U]。}
{当等于c的分量还没有找到且U>=L时，继续查找}
While (not Found) and (U>=L) do
Begin
I:=(U+L) div 2; {找数组的中间分量}
If c=A[I] then Found:=Ture
else if c>A[I] then L:=I+1
else U:=I-1;
End;
If Found then B_Search:=1
else B_Search:=0;
End;
容易理解，在最坏的情况下最多只要测 A 中的 k+1(k=logm, 这里的 log 以 2 为底，下同 ) 个分量，就判断 c 是否在 A 中。
算法 Search 和 B_Search 解决的是同一个问题，但在最坏的情况下（所给定的 c 不在 A 中），两个算法所需要检测的分量个数却大不相同，前者要 m=2 k 个，后者只要 k+1 个。可见算法 B_Search 比算法 Search 高效得多。
以上例子说明：解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随之不同，即复杂性不同。
上图是运行这两种算法的时间曲线。该图表明，当 m 适当大（ m>m0 ）时，算法 B_Search 比算法 Search 省时，而且当 m 更大时，节省的时间急剧增加。
不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。