问题1描述
给一个已经排序的数组，其中有N个互不相同的元素。要求使用最小的比较次数找出其中的一个元素。(你认为二分查找在排序数组里找一个元素是最优的算法的吗？)
不需要太多的理论，这是一个典型的二分查找算法。先看下面的代码：
int BinarySearch(int A[], int l, int r, int key) |
03 | { |
04 | int m; |
05 | while( l <= r ) |
06 | { |
07 | m = l + (r-l)/2; |
08 |
09 | if( A[m] == key ) //第一次比较 |
10 | return m; |
11 |
12 | if( A[m] < key ) // 第二次比较 |
13 | l = m + 1; |
14 | else |
15 | r = m - 1; |
16 | } |
17 |
18 | return -1; |
19 | } |
理论上，我们最多需要 logN+1 次比较。仔细观察，我们在每次迭代中使用两次比较，除了最后比较成功的一次。实际应用上，比较也是代价高昂的操作，往往不是简单的数据类型的比较。减少比较的次数也是优化的方向之一。
下面是一个比较次数更少的实现：
在while循环中，我们仅依赖于一次比较。搜索空间( l->r )不断缩小，我们需要一个比较跟踪搜索状态。
需要注意的，要保证我们恒等式（A[l] <= key & A[r] > key）正确，后面还会用到循环不变式。
04 | int BinarySearch(int A[], int l, int r, int key) |
05 | { |
06 | int m; |
07 | while( r - l > 1 ) |
08 | { |
09 | m = l + (r-l)/2; |
10 |
11 | if( A[m] <= key ) |
12 | l = m; |
13 | else |
14 | r = m; |
15 | } |
16 | if( A[l] == key ) |
17 | return l; |
18 | else |
19 | return -1; |
20 | } |
问题4描述
有一个已排序的数组（无相同元素）在未知的位置进行了旋转操作，找出在新数组中的最小元素所在的位置。
例如：原数组 {1,2,3,4,5,6,7,8,9,10}， 旋转后的数组可能是 {6,7,8,9,10, 1,2,3,4,5 }，也可能是 {8,9,10,1,2,3,4,5,6,7 }
我们不断的缩小 l 左指针和 r 右指针直到有一个元素。把上面划横线的作为第一部分，剩下的为第二部分。如果中间位置m落在第一部分，即A[m] < A[r] 不成立，我们排序掉区间 A[m+1 ... r]。 如果中间位置m落在第二部分，即 A[m]<A[r]成立，我们缩小区间至 A[m+1 .... r ]。 直到搜索的区间大小为1就结束。int BinarySearchIndexOfMinimumRotatedArray(int A[], int l, int r) |
02 | { |
03 | int m; |
04 |
05 | // 先决条件: A[l] > A[r] |
06 | if( A[l] <= A[r] ) |
07 | return l; |
08 |
09 | while( l <= r ) |
10 | { |
11 | //终止条件 |
12 | if( l == r ) |
13 | return l; |
14 |
15 | m = l + (r-l)/2; // 'm' 可以落在第一部分或第二部分 |
16 |
17 | if( A[m] < A[r] ) |
18 | // (m < i <= r),可以排除 A[m+1 ... r] |
19 | r = m; |
20 | else |
21 | // min肯定在区间 (m < i <= r), |
22 | // 缩小区间至 A[m+1 ... r] |
23 | l = m+1; |
24 | } |
25 | return -1; |
26 | } |
27 |
28 | int BinarySearchIndexOfMinimumRotatedArray(int A[], int size) |
29 | { |
30 | return BinarySearchIndexOfMinimumRotatedArray(A, 0, size-1); |
31 | } |
