C++折半查找的基本思想和步骤

Question

急求C++折半查找的基本思想和步骤<详细的>

Answer 1

你对对半查找理解错了，你的min,max应该是下标而不是值原理：类似于二分法解方程，二分查找首先比对序列中间的数是否是要找的数，如果不是，由于是有序数列，则看其在左侧区间还是右侧区间，舍弃不在的那一半区间，然后在剩余的区间重复刚才的办法，直到找到该数，由于每次舍弃一半的数据量，所以查找效率较高。描述：设三个变量 left,right,middle分别为序列的两侧下标和中间下标，当判断出不在左侧区间，则 left=middle+1 ，从而利用右侧一半构造出一个新区间，否则 right=middle-1，利用左边一侧构造新区间，然后重复刚才过程，如此下去，要么找到数据，要么left>right，此时也应该停止查找，说明序列中没有该数。