折半查找的基本过程是:设Row.hgh是当前的查找 区间,首先确定该区间的中点位置md(ow+hgh2;然 后将待查的值与R| mid]. keyl比较 (1)若 TImid. key=k,则查找成功并返回该元素的逻 辑序号; (2)若 Rmid. key>k,则由表的有序性可知R|mid.n 1Jkey均大于k,因此若表中存在关鍵字等于k的元素,则该 元素必定在位置md左子表R|0.mid-1中,故新的查找区间 是左子表R.mnid-1l (3)若 Rmid. key<k,则要查找的k必在位置md的右 子表R|md+1.n-1中,即新的查找区间是右子表 R[mid+1.n-1l。 下一次查找是针对新的查找区间进行的
折半查找的基本过程是：设R[low..high]是当前的查找 区间，首先确定该区间的中点位置mid=(low+high)/2；然 后将待查的k值与R[mid].key比较： （1）若R[mid].key=k，则查找成功并返回该元素的逻 辑序号； （2）若R[mid].key>k，则由表的有序性可知R[mid..n- 1].key均大于k，因此若表中存在关键字等于k的元素，则该 元素必定在位置mid左子表R[0..mid-1]中，故新的查找区间 是左子表R[0..mid-1]； （3）若R[mid].key<k，则要查找的k必在位置mid的右 子表R[mid+1..n-1]中，即新的查找区间是右子表 R[mid+1..n-1]。 下一次查找是针对新的查找区间进行的
public int BinSearch(int k) /拆半查找算法 int low=0, high=length-1, mid while (low<=high) /当前区间存在元素时循环 i mid=(lowthigh)/2 /求查找区间的中间位置 if(R| mid key=k)查找成功返回其逻辑序号md+1 return mid+1 /找到后返回其逻辑序号mid+1 if (r[mid. key>k) /继续在R[ow.md-1中查找 high=mid-1 else //RImid. key<k low=mid+1 /继续在Rmd+1high中查找 return U; /若当前查找区间没有元素时返回0
public int BinSearch(int k) //拆半查找算法 { int low=0,high=length-1,mid; while (low<=high) //当前区间存在元素时循环 { mid=(low+high)/2; //求查找区间的中间位置 if (R[mid].key==k) //查找成功返回其逻辑序号mid+1 return mid+1; //找到后返回其逻辑序号mid+1 if (R[mid].key>k) //继续在R[low..mid-1]中查找 high=mid-1; else //R[mid].key<k low=mid+1; //继续在R[mid+1..high]中查找 } return 0; //若当前查找区间没有元素时返回0 }
折半查找过程可用二叉树来描述: 把当前查找区间的中间位置上的记录作为根; 左子表和右子表中的记录分别作为根的左子树和右子 树 称为描述折半查找的判定树或比较树
折半查找过程可用二叉树来描述： 把当前查找区间的中间位置上的记录作为根； 左子表和右子表中的记录分别作为根的左子树和右子 树。 称为描述折半查找的判定树或比较树
R|0.10的折半查线的判定树(n=1)
5 2 8 0 3 6 9 -∞～-1 1 2～3 4 5～6 7 8～9 10 0～1 1～2 3～4 4～5 6～7 7～8 9～10 10～∞ < > = < = > < = > < > = < > = < > = < = > < > = < = > < > = < = > R[0..10]的折半查线的判定树(n=11)
例81对于给定11个数据元素的有序表 2,3,10,15,20,25,28,29,30,35,40},采用折半查找,试问: (1)若查找给定值为20的元素,将依次与表中哪些 元素比较? (2)若查找给定值为26的元素,将依次与哪些元素 比较? (3)假设查找表中每个元素的概率相同,求查找成 功时的平均查找长度和查找不成功时的平均查找长度
例 8.1 对 于 给 定 11 个 数 据 元 素 的 有 序 表 {2,3,10,15,20,25,28,29,30,35,40}，采用折半查找，试问： （1）若查找给定值为20的元素，将依次与表中哪些 元素比较？ （2）若查找给定值为26的元素，将依次与哪些元素 比较？ （3）假设查找表中每个元素的概率相同，求查找成 功时的平均查找长度和查找不成功时的平均查找长度