折半（對半）搜尋算法

二分搜尋算法要求有序表采用順序存儲，其中折半搜尋（又稱折半搜尋）是二分搜尋的一個特例，設目前搜尋的子表為（Aleft，Aleft+1，Aleft+2，……，Aright），令

m=（left+right）/ 2。這種二分搜尋被稱為對半搜尋。對半搜尋算法将表劃分成幾乎相等大小的兩個字表。

下面給出對半搜尋的遞歸算法（使用模闆，具體應用時可以再進行相應修改）：

遞歸函數的效率往往較低，常希望得到相應的疊代算法，下面給吃對半搜尋的疊代算法：