折半（对半）搜索算法

二分搜索算法要求有序表采用顺序存储，其中折半搜索（又称折半搜索）是二分搜索的一个特例，设当前搜索的子表为（Aleft，Aleft+1，Aleft+2，……，Aright），令

m=（left+right）/ 2。这种二分搜索被称为对半搜索。对半搜索算法将表划分成几乎相等大小的两个字表。

下面给出对半搜索的递归算法（使用模板，具体应用时可以再进行相应修改）：

递归函数的效率往往较低，常希望得到相应的迭代算法，下面给吃对半搜索的迭代算法：