问题：在有序的数组中搜索
给定一个包含n的数组E，并给定一个值K，请找到 K=E[index]的一个索引，如果K不在数组中，则返回-1作为答案

策略A
输入数据和数据结构：无排序数组
顺序搜索

算法A
int seqSearch(int[] E, int n, int K)

分析A
W(n) = n
A(n) = q [(n+1)/2] + (1-q) n

优化A
用于搜索未排序的数组
F (n) = n
算法A是最优的。

策略B
输入数据和数据结构：按非递减顺序排序的数组
顺序搜索

算法B
int seqSearch(int[] E , int n , int K)

分析 B
W (n) = n
A (n)=q [(n +1)/2]+ (1 - q) n

B的优化
它没有利用条目是有序的这一事实 我们能否修改算法，使其减少工作？

策略C
输入数据：以非递减顺序排序的数组 顺序搜索。
一旦遇到大于K的数组，算法就可以终止，答案是-1

int seqSearchMod(int[] E, int n, int K)
 int ans, index;
 ans =1; // Assume failure.
 for (index = 0; index < n; index++)
     if (K > E[index])
         continue;
     if (K < E[index])
         break; // Done!
     // K == E[index]
     ans = index; // Find it
     break;
 return ans;

策略D
首先将K与数组中间的条目进行比较
通过一次比较消除一半的条目
递归地应用同样的策略

算法D：二分法搜索
输入：E，first，last和K，都是整数，其中E是一个有序的数组，范围是first，...，last，而K是要寻找的

输出：索引，如果K在E的first, ..., last范围内，则E[索引]=K；如果K不在E的这个范围内，则索引=-1。

int binarySearch(int[] E, int first, int last, int K)
  if (last < first)
       index = -1;
  else
      int mid = (first + last)/2
      if (K == E[mid])
         index = mid;
      else if (K < E[mid])
         index = binarySearch(E, first, mid-1, K)
      else
       index = binarySearch(E, mid+1, last, K);
 return index