数据结构复习资料
8.2.2二分查找 二分查找 1.二分查找的基本思想 二分查找的基本思想 二分查找，也称折半查找，是一种高效率的查找方法。 但要求表中元素必须按关键字有序(升序或降序)。不妨假 设表中元素为升序排列。二分查找的基本思想是：首先将 待查值K与有序表array[0]到array[n-1]的中点mid上的关键 字array[mid].key进行比较，若相等，则查找成功；否则， 若array[mid].key>k , 则在array[1]到array[mid-1]中继续查 找，若有array[mid].key<k , 则在array[mid+1]到array[n-1] 中继续查找。每通过一次关键字的比较，区间的长度就缩 小一半，区间的个数就增加一倍，如此不断进行下去，直 到找到关键字为K的元素；若当前的查找区间为空(表示查 找失败)。