08-算法设计

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

问题描述：给定n个元素，这些元素是有序的（假定为升序），从中查找特定元素x。

算法思想：将有序序列分成规模大致相等的两部分，然后取中间元素与特定查找元素x进行比较，如果x等于中间元素，则查找成功，算法终止；如果x小于中间元素，则在序列的前半部分继续查找，即在序列的前半部分重复分解和治理操作；否则，在序列的后半部分继续查找，即在序列的后半部分重复分解和治理操作。

算法设计：用一维数组S[]存储该有序序列，设变量low和high表示查找范围的下界和上界，middle表示查找范围的中间位置，x为特定的查找元素。

（1）初始化。令low=0，即指向有序数组S[]的第一个元素；high=n−1，即指向有序数组S[]的最后一个元素。

（2）middle=（low+high）/2，即指示查找范围的中间元素。

（3）判定lowhigh是否成立，如果成立，转第4步，否则，算法结束。

（4）判断x与S[middle]的关系。如果x=S[middle]，则搜索成功，算法结束；如果x>S[middle]，则令low=middle+1；否则令high=middle−1，转为第2步。