C语言名题精选百则——查找
?
?
尊重他人的劳动，支持原创
本篇博文，D.S.Qiu将对《C语言名题精选百则——排列，组合和集合》进行整理推出，不光只是书上的名题，还会依据互联网的资源进行不断补充，加强。等全书各个章节都整理完，会做一个总汇。如果你有建议、批评或补充，请你不吝提出（email:gd.s.qiu@gmail.com，或者直接在本文末评论）。你的支持和鼓励（一个人整理真的很累，几度想放弃），我将渐行渐远！
《排列，组合和集合》主要是介绍了关于有序数组的几个问题，相对简单比较好能理解（点击查看更多数组和字符串问题），主要是对效率的改进，但是要是尽善进美还有待不断的挖掘。下一篇是《排序》（其实就是数论的一些问题），更多关注：http://dsqiu.iteye.com。
问题4.1寻找脚码(ISEARCH.C )
?
已知一个整数数组x[]，其中的元素彼此都不相同，而且也已经从小到大排列好。请用 比较大小、相等的方式编写一个程序，找出给定的数组中是否有一个元素满足x[i]=i的关系。举例而言，如果x[]={-2，-1，3，7，8}, x[3]=3,因此3就是答案。
?
【说明】
用笨方法，一个循环就可以找出答案，如程序4-1所示。
?
【程序】
?
程序4-1
for (index = -1, i=0; i<n, i++)
if (x[i] == i) {
index = i; break;
}
if (index >= 0)
printf("\nFound at x[%d]", index);
else
printf ("\nNot Found")
?
这个程序在最坏的情况下，for —共绕了 n圈，作了 n次比较，但却没有用到x[]的元素已经排列好的条件。事实上，如果输入有n个元素，应该可以写出与log2n次成正比的比较的程序，关键是X[]的元素是排好顺序的。
?
?
【解答】
如果要在一个己经排列好的数组中查找元素，那多半会用到二分查找法，不过这个题 目有点不一样，因为“不知道”要找的数据的值，因此要有点变化才行。首先，要注意两 种情况：
(1)如果x[i]>i,那么对于比i大的任何一个脚码k而言，都会得到x[k]>k,因此 一旦发现了某个i满足x[i]>i时，满足x[j]=j的j就一定只会发生在j<i的所在。
(2)如果x[i]<i,那么对于比i小的任何一个脚码k而言，都会得到x[k]<k,于是 一旦发现了某个i满足x[i]<i时，满足x[j]=j的j就一定只会发生在j>l的所在。
基于上述两种情况，程序就可以找出中间的元素，令它的脚码为middle,比较x[middle] 与middle是否相等，相等的话就找到解答方法了。如果不相等，就看x[middle]>middle 是否成立，如果成立，那么满足x[i]=i就一定在middle的左边；反之，则在右边。所以这 是一个标准的二分查找法（Binary Search)的变形。
程序要作多少次比较呢？在while中每一个循环都比较两次，一次比相等，一次比大 于。在最坏的情况下，while —共会绕log2n圈，因为每一次要查找的部分都减半，所以总
共会用21og2n次比较。这一项分析与二分查找法完全相同，肯定会比在问题说明中的方法快。
?
?
【问题实现】
?
【习题】(1)另一个常见的写法是在bound()函数中用Fibonacci数1,1，2,3，5，8，13，…，而不是1,2^1,2^2,2^3,请把程序改成这个做法，看看程序效率有何差异。(2)如果数组中有n个元素，请问这个程序一共作了多少个比较？(3)为了方便起见，把~定成该类型的极大值，如果-只是比数组中每一个元素都大, 而又不知道这个值是多少，这个程序还輯够正常运行吗？为什么？如果不能，用什么方法 克服?程序效率会不会大打折扣？请举一个程序不能正常运行的例子（如果程序真的不能正考运行的话)。(4)如果薮组中除了之外，其他元素都不相同；在这种情况下有没有办法找出~的 值是卄么？需要很多次比较吗？请在这个条件下重做第（3)题。?
问题4.4寻找扱小值（CYCLEMIN.C )
一个数组是以循环顺序排列的，也就是说在数组中有某个元素i,从Xi开始有这样的的关系，X0<X1<X2<…<Xi-1<Xi<…<Xn<X0。例如，8,10,14,15,2,6 这 7 个元素就是循环顺序排列的，因为从2开始为递增，到了最后一个元素就转换为第1个元素，再 依顺序递增。换句话说，如果把Xi,Xi+1，…，Xn取出，并且接到数组开头，于是就是一个从小到大的顺序（这不是个旋转的动作吗？）。编写一个程序，接收一个以循环顺序排列的数组，把它的极小值找出来，以上面数据为例，程序应该会输出2
【说明】因为从X()起顺序是递增的，一直到极小值出现，马上就会出现相反顺序，于是很多人 马上就会想出这个做法：for ( i = 1 ； i < n && x [i ] >-=x [i-1 ] ; i + +)一旦这个循环停下来了，如果i等于n那就表示每一个元素都大于在它前面的那一个, 因而极小值为x[0];但若i<n,且x[i]<x[i-l],因此极小值为x[i]。这是个正确的做法，但效率却不够高，因为在最坏的情况下可能要做n-1次的比较。 不过，这个数组严格说还是有顺序性的，根据这一特性应该可以找出更好、更快的方法， 不妨试试看。
【解答】解决的办法还是二分查找法，也许会质疑这个数组并没有完全依顺序排列。不错，但不要以为二分查找法只能做那么一点事，事实上，只要能够把问题剖成两部分，而有办法判定解答在其中的一部分的话，这就是个二分查找法。例如，现在处理XL与XM之间的元素（含两个端点），取中间元素XM，M = (L + R)/2。于是就会出现下面两种情况：(1) xL<=xM：换句话说，xM比左边的元素大，因为从左到右是递增的，一直到极小值出现才不升反降，但xL<=xM明确指出；xL到xM是递增，因而极小元素不会在L与M之间，因此下一个L就是M +1。(2)xL>xM：因为从xL起是递增，一直到极小值出现才会降下来，然后自极小值起才再度上升，而且XL>=XR。现在有XL>Xm,这表示L与M中一定有极小值才会出现这个现象，所以下一个R是M。就这样一直反复，总会出现L=R的时候，于是\就是极小值，L就是它的所在。在程序CYCLEMIN.C中，left、right与mid分别取代此地为L、R与M,而且cyclejnin() 函数只返回极小值的脚码，而不是返回极小值，所以要找出极小值，就要用该脚码取出数 组中对应的元素。
【问题实现】?问题4.7 3个数组的共同元素（SEARCH3.C )
有3个数组x[]、y[]与z[]，各有x、y与z个元素，而且三者都已经从小到大依序排 列。编写一个程序，找出值最小的共同元素（也就是同时在3个数组中出现，并且值最小的元素)；但若没有共同元素，请显示合适的信息。
【说明】通常寻找数据的工作都是给了一个数据，看看在某个数组中有没有它，但是这个问题却是另一个目的，要找出一个共同的元素。其实在实际应用中这种类型是屡见不鲜的。例 如，警察知道犯人是台北市人，有大学学历，有窃盗前科，因此就可能从台北市得到这个 台北人的档案，从教育部取得历年大学毕业生的档案，再从警察局取得有窃盗前科的人的 档案，如果这些档案已经依人名从小到大排好了，那么找出嫌疑人的工作就与本题差不多， 所不同的是：第一，只要找出第一个，而警察局可能要找出所有的；第二，用数组处理，所 以得知该元素个数，而警察局收到的是档案，也许不知道各个档案有多少笔数据而已。 因为不知道要找的是什么，所以二分查找法没有多大用处，要另外想办法来解题，据我所知，最多用3min(x，y，z)次比较就可以决定答案，更重要的是程序将不超过10列，所以要往深处思考。
【问题实现】
?这是绝大多数程序员都会想到的办法，但是这个方法却要比较与n^4成正比的次数是方阵的列数)。为什么？方阵有n^2个元素，每一个元素最多比较n^2次，所以是n^2 次。当然，事实上不会有那么多次，会少一些，但总是与n^4成正比。做这个题目的基本要求是打破比较n^4次的限制，例如n^3次，或进一步比较n^2次。与n^2 成正比的比较次数是最低限度了，因为矩阵本身就有n^2个元素，至少每一个元素都会比次。
【问题实现】?
参考：
C语言明天精选百则 冼镜光著
?
