姓名:吕彬 学号:16130140354
【嵌牛导读】 二分查找也属于顺序表查找范围,二分查找也称为折半查找。二分查找(有序)的时间复杂度为O(LogN)。
【嵌牛鼻子】从二分查找的定义我们可以看出,使用二分查找有两个前提条件:1,待查找的列表必须有序。2,必须使用线性表的顺序存储结构来存储数据。
【嵌牛提问】 那么什么是二分查找呢?
【嵌牛正文】那么什么是二分查找呢?
二分查找的基本思想是, 在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到找到为止。
方法分析:折半查找先以有序数列的中点位置为比较对象,比较会产生3种情况,一种是待查找值大于中点位置的数,此时我们要把比较区间缩小为有序数列的后半部分;一种是待查找值小于中点位置的数,此时我们要把比较区间缩小为有序数列的前半部分;一种是待查找值等于中点位置的数,此时查找成功。这样不断比较,直到查找成功或者区间小于0,就停止查找!数据结构设计:有序数列:用一个数组data[size]来存放。区间:区间用数组的两个下标表示。
用整型low,high下标来表示区间的前端点,后端点。mid表示数组的中间位置下标。如: 7 14 18 21 23 29 31 35 38 52 ↑ low ↑ mid ↑ high (mid=(low+high)/2)
主要代码截图如下: