在开始今天的算法题之前，先介绍一个概念：循环不变式
这个概念主要用来检验算法的正确性。原文如下：
We use loop invariants to help us understand why an algorithm is correct. We must show three things about a loop invariant:
Initialization: It is true prior to the first iteration of the loop.
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
翻译如下（笑哭.jpg）
在循环的第一轮迭代开始之前，应该是正确的。
=＞初始化（循环第一次迭代之前）的时候，A[1 ‥ j -1]的“有序性”是成立的；如果在循环的某一次迭代开始之前它是正确的，那么在下一次迭代开始之前，它也应该保持正确；
=＞在循环的每次迭代过程中，A[1 ‥ j -1]的“有序性”仍然保持；当循环结束时，不变式给了我们一个有用的性质，它有助于表明算法是正确的。
=＞循环结束的时候，A[1 ‥ j -1]的“有序性”仍然成立。
apparently,这和我们数学里面的数学归纳法看起来就很像了。
相似之处在于数学归纳法中，要证明某一个性质是成立的，必须首先证明其基本情况和某一个归纳步骤是成立的。
这儿证明循环不变式在第一次迭代开始之前是成立的，就有点类似于对基本情况的证明；证明不变式在各次迭代之间保持成立，就有点类似于归纳法中对归纳步骤的证明。
不过需要注意的是：有关循环不变式的三个性质最重要的可能是第三个性质，因为我们用循环不变式的目的就是证明算法的正确性。数学归纳法中的归纳步骤是无穷使用的，而在证明循环不变式时当循环结束就会停止归纳。
OK，那么现在开始解决今天的算法题了。
题目贴出来先：
输入：n个数的一个序列A=<a1,a2,……,an>和一个值v。
输出：下标i，使得v=A[i]；或者当v不在A中出现时，v为特殊值NIL。
这个题目其实和之前的那个插入的题也差不多，就是一个扫描配对查找。听easy的。
附上代码：
#include <iostream>
using namespace std;
int search(int arr[],int v,int len);
int main(){
int Arr[5],v;//此处假设数组长度为5
cout<<"please input 5 number"<<endl;
for(int i=0;i<5;i++)
cin>>Arr[i];
int length=sizeof (Arr)/sizeof (Arr[0]);//int length=5;
cout<<"please input the value of v"<<endl;
cin>>v;
int k;//接收返回值
k=search(Arr,v,length);//调用search方法
cout << "back index:"<<k<<endl;//数不存在则输出404
return 0;
}
int search(int arr[],int v,int len){
int i;
for(i=0;i<len;i++){
if(arr[i]==v){
return i;
break;
}
}
if(i=len-1)//无此数，则循环完
return 404;
}
今天贴代码的方式和昨天是不是感觉不一样了，昨天百度了一波简书贴代码的方式，原来简书支持部分markdown编辑，在个人设置里面设置就可以了。至于markdown的语法规则，百度一下就出来啦。https://www.appinn.com/markdown/
运行结果展示：
明天的算法：用分治法解决DAY1的排序题，设计更高效的算法。
输入：n个数的一个序列<a1,a2,……,an>
输出：输入序列的一个排列< a1',a2',……,an '>,满足 a1'≤a2 '≤ …… ≤ an'
回顾：[DAY1]http://www.jianshu.com/p/b4e20b4a7a62
继续：[DAY3]http://www.jianshu.com/p/01d17607b719
