《算法学习--排序与查找》由会员分享，可在线阅读，更多相关《算法学习--排序与查找（27页珍藏版）》请在金锄头文库上搜索。
1、算法学习-排序与查找作者：qinzhaokun二分查找我们都知道二分查找算法，实际上二分查找以及其扩展应用是很广泛的。这里收集了一些和二分查找有关的有趣问题。强烈建议大家看完问题后最小化浏览器，先尝试自己去解决，然后再看代码，问题都不是太难。问题 1 描述给一个已经排序的数组，其中有 N 个互不相同的元素。要求使用最小的比较次数找出其中的一个元素。(你认为二分查找在排序数组里找一个元素是最优的算法的吗？)不需要太多的理论，这是一个典型的二分查找算法。先看下面的代码：int BinarySearch(int A, int l, int r, int key)int m;while( l key/
2、 边界: |r - l| = 1/ 输入: Al . r-1int BinarySearch(int A, int l, int r, int key)int m;while( r - l 1 )m = l + (r-l)/2;if( Am r )不断缩小，我们需要一个比较跟踪搜索状态。需要注意的，要保证我们恒等式（Al key）正确，后面还会用到循环不变式。问题 2 描述给一个有 N 个互不相同的元素的已排序数组，返回小于或等于给定 key 的最大元素。 例如输入为 A = -1, 2, 3, 5, 6, 8, 9, 10 key = 7,应该返回 6.分析：我们可以用上面的优化方案，还是保
3、持一个恒等式，然后移动 左右两个指针。最终 left指针会指向 小于或等于给定 key 的最大元素(根据恒等式 Al key)。- 如果数组中所有元素都小于 key，左边的指针 left 会一直移动到最后一个元素。- 如果数组中所有元素都大于 key，这是一个错误条件，无答案。- 如果数组中的所有元素都 1 )m = l + (r - l)/2;if( Am keyint GetRightPosition(int A, int l, int r, int key)int m;while( r - l 1 )m = l + (r - l)/2;if( Am = key and Al keyint
4、 GetLeftPosition(int A, int l, int r, int key)int m;while( r - l 1 )m = l + (r - l)/2;if( Am = key )r = m;elsel = m;return r;int CountOccurances(int A, int size, int key)/ 找出边界int left = GetLeftPosition(A, -1, size-1, key);int right = GetRightPosition(A, 0, size, key);/ key 有可能不存在，需要判断return (Aleft
5、= key 问题 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 落在第一部分，即 Am Arif( Al numsmid if(rchildamax)max=rchild;if(max!=i)swap(ai,amax);HeapAdjust
6、(a,max,size); /避免调整之后以 max 为父节点的子树不是堆 void BuildHeap(int *a,int size) /建立堆int i;for(i=size/2;i=1;i-) /非叶节点最大序号值为 size/2HeapAdjust(a,i,size); void HeapSort(int *a,int size) /堆排序int i;BuildHeap(a,size);for(i=size;i=1;i-)/cout=nint c = new intk + 1;for (int i = 0; i = 0; i-) bcai - 1 = ai;/ CAi-1 就代表小于
7、等于元素 Ai的元素个数，就是 Ai在 B 的位置cai-;System.out.println(“n 计数排序第 4 步后,临时数组 C 变为：“);for (int n : c) System.out.print(n + “ “);System.out.println(“n 计数排序第 4 步后,数组 B 变为：“);for (int t : b) System.out.print(t + “ “);System.out.println();System.out.println(“*n“);public static int getMaxNumber(int a) int max = 0;
8、for (int i = 0; i using namespace std;/对数组 arr计数排序，根据 exp 指定的位int countSort(int arr, int n, int exp)int outputn; / 结果数组int i, countn ;for (int i=0; i = 0; i-)outputcount (arri/exp)%n - 1 = arri;count(arri/exp)%n-;/ 再将排序结果复杂到 arrfor (i = 0; i using namespace std;/第一遍求最小值的结果用树表示struct nodeint key;node
9、 *next;/指向同一层中的下一个元素node *p;node *left;node *right;node(int k):key(k),next(NULL),p(NULL),left(NULL),right(NULL);/求第二小值int Find_S2(node *head)node *p, *q, *r, *t;/step1：求最小值/两两比较，较小的一个进入下一轮，这个循环当只剩下一个元素时结束while(head-next != NULL)/从第一个元素开始，head 指向比完后较小的那一组数据中的第一个p = head;head = NULL;while(p)/如果这组数据有奇数
10、个，最后一个元素直接晋级if(p-next = NULL)r = new node(p-key);r-left = p;p-p = r;p = p-next;/p 与 p-next 比较，较小的元素晋级elseq = p-next;r = new node(min(p-key, q-key);r-left = p;r-right = q;p-p = r;q-p = r;p = q-next;/head 指向比完后较小的那一组数据中的第一个，t 用于把 head 指向的数据链成链表if(head = NULL)head = r;t= head;elset-next = r;t = r;/step
11、2：求最第二小值/Min 用于存储最小值，Min2 用于存储第二小值int Min = head-key, Min2 = 0x7fffffff;/从根结点向下比较p = head;/比较到叶子结点时循环结束while(p-left != NULL)/当前结点的值来源于右孩子if(p-right p = p-right;/当前结点的值来源于左孩子else/由左孩子直接晋级的情况if(p-right)Min2 = min(Min2, p-right-key);p = p-left;return Min2;/测试int main()int A8 = 0;node *head = NULL;/生成 8 个随机测试数据for(int i = 0; i next = head;head = p;/运行算法并输出结果coutFind_S2(head)endl;return 0;问题 4 描述有一个已排序的数组（无相同元素）在未知的位置进行了旋转操作，找出在新数组中的最小元素所在的位置。
