5.2.2 分支程序设计方法举例

　 程序的分支一般用条件转移指令来产生，下面来看一个例子。

　　例5.7 在附加段中，有一个按从小到大顺序排列的无符号数数组，其首地址存放在DI寄存器中，数组中的第一个单元存放着数组长度。在AX中有一个无符号数，要求在数组中查找（AX），如找到，则使CF = 0，并在SI中给出该元素在数组中的偏移地址；如未找到，则使CF = 1。

　　本例是一个已经排序的数组，可以采用折半查找法以提高查找效率。
　　折半查找法先取有序数组的中间元素与查找值相比较，如相等则查找成功；如查找值大于中间元素，则再取高半部的中间元素与查找值相比较；如查找值小于中间元素，则再取低半部的中间元素与查找值相比较；如此重复直到查找成功或最终未找到该数（查找不成功）为止。折半查找法的效率高于顺序查找法，对于长度为N的表格，顺序查找法平均要作N/2次比较，而折半查找法的平均比较次数为 log2N。所以，如果数组长度为100，则顺序查找法平均要作50次比较，而折半查找法平均作7次比较就可以了。

　　动画表示了折半查找算法的程序框图。

　　给出的程序首先把查找值与数组的第一个元素和最后一个元素相比较，如果找到或者该数小于第一个元素或大于最后一个元素则结束查找；否则从SEARCH开始折半查找。SEARCH以前的工作在动画中未表示出来。从SEARCH开始，首先把数组长度作为数组中间元素的下标，把它从数组的第一个单元中取出来并使它成为偶数，然后把下标加到DI中以形成数组中间元素的地址，并且开始比较查找。如果比较相等，则转至ALL_DONE结束查找，否则要确定下一步的查找是在数组的低半部还是高半部中进行。它们所要做的工作是：首先检查下标是否等于2，如等于2，则说明整个查找失败，应把CF置1并转至ALL_DONE结束查找工作；其次，把下标除以2，以便作进一步的折半查找，然后使下标形成偶数值；如果要在低半部查找，则从当前的地址（DI）中减去下标值（SI）以形成新的查找地址；如果要在高半部查找，则把下标值加到当前地址中。以上过程重复进行，直到下标值减到2或者查找值找到为止。