爱站程序员基地- 折半查找也称二分查找（Binary Search）
它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。
基本思想：是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x. - 递归（recursion）：递归常被用来描述以自相似方法重复事物的过程，在数学和计算机科学中，指的是在函数定义中使用函数自身的方法。（A调用A）
- 迭代（iteration）：重复反馈过程的活动，每一次迭代的结果会作为下一次迭代的初始值。（A重复调用B）
迭代版：
#include <iostream>using namespace std;//声明 迭代 函数int search_I(int *a,const int x,const int n);int main() {int m[]= {1,2,3,4,5,6,7,8,9};int answer,num=4;//num是要搜索的数字if((answer=search_I(m,num,9))<0) {cout<<\"迭代算法没找到!\"<<endl;} else {cout<<\"迭代算法：在m[\"<<answer<<\"]找到\"<<num<<endl;}return 0;}int search_I(int *a,const int x,const int n) {int left = 0,right = n-1;while(left<=right) {int middle =(left+right)/2;if(x<a[middle]) right =middle-1;else if(x>a[middle]) left =middle+1;else return middle;}return -1;}
递归版：
#include <iostream>using namespace std;//声明 递归 函数int search_R(int *a,const int x,const int left,const int right);int main() {int m[]= {1,2,3,4,5,6,7,8,9};int answer,num=4;//num是要搜索的数字if((answer=search_R(m,num,0,8))<0) {cout<<\"递归算法没找到!\"<<endl;} else {cout<<\"递归算法：在m[\"<<answer<<\"]找到\"<<num<<endl;}int search_R(int *a,const int x,const int left,const int right) {if(left<=right) {int middle =(left+right)/2;if(x<a[middle]) return search_R(a,x,left,middle -1);else if(x>a[middle]) return search_R(a,x,middle+1,right);else return middle;}return -1;}
- 递归是一个树结构，其过程相当于树的深度优先遍历。迭代是一个环结构，从初始状态开始，每次迭代都遍历这个环，并更新状态，多次迭代直到到达结束状态。
- 为什么使用迭代而不用递归呢？
理论上递归和迭代时间复杂度方面是一样的，但实际应用中递归比迭代效率要低。使用递归时每调用一次，就需要在栈上开辟一块空间，而使用迭代就不需要了，因此，很多时候设计出了递归算法，还要想法设法修改成迭代算法。
