s822有序表的折半检索 (一)折半检索算法 long Bin Search(int all, long n, int key) {*有序表(升序)的折半查找的非递归算发 a—输入量,一维数组,充当有序线形表(连续结构),表中 元素按关键字key的升序排列,O号位置空置 key输入量,待查关键字 返回—返回所找到的关键字的位置号,找不到时返回0 long low, high, mid low-l; high-pL-last
21 §8.2.2 有序表的折半检索 (一)折半检索算法 long BinSearch(int a[], long n, int key) {/*有序表（升序）的折半查找的非递归算发 a[]——输入量，一维数组，充当有序线形表（连续结构），表中 元素按关键字key的升序排列，0号位置空置 key——输入量，待查关键字 返回——返回所找到的关键字的位置号，找不到时返回0 */ long low, high, mid; low=1;high=pL-last;
§822有序表的折半检索 (一)折半检索算法 while(low<=high) md=(ow+high)/2;∥求中点 if (key==amid])return mid else if(key<a[mid)high=mid-1;/下次在前半部分查找 else low=mid+1;//下次在后半部分查找 return o /*查找失败* )/Bin Search 22
22 §8.2.2 有序表的折半检索 (一)折半检索算法 while(low<=high) { mid=(low+high)/2; //求中点 if (key==a[mid] ) return mid; else if ( key < a[mid]) high=mid-1; //下次在前半部分查找 else low=mid+1; //下次在后半部分查找 } return 0; /*查找失败*/ }/BinSearch
§8.22有序表的折半检索 (一)折半检索算法 long BinSearch2(int all, long low, long high, int key) {/*有序线形表(连续存储结构)的折半查找的递归算法 a[-同前 long, high-—输入量,指定查找范围,分别为有序表的査找范围的低端 和高端的序号 返回同前 long mid 23
23 §8.2.2 有序表的折半检索 (一)折半检索算法 long BinSearch2(int a[], long low, long high, int key) {/*有序线形表（连续存储结构）的折半查找的递归算法 a[]----同前 long, high——输入量，指定查找范围，分别为有序表的查找范围的低端 和高端的序号 返回——同前 */ long mid;
§8.22有序表的折半检索 (一)折半检索算法 i(low>high) return0;∥查不到 mid=(low+high)/2 if(key==amid return mid ikey<a[mid) return Bin Search2(a, low. mid-1,key);/在前半部分查找 else return Bin Search2(a,mid+l,high,key),∥在后半部查找 i/inSearch 24
24 §8.2.2 有序表的折半检索 (一)折半检索算法 if(low>high) return 0; //查不到 mid=(low+high)/2; if(key==a[mid]) return mid; if(key<a[mid]) return BinSearch2(a, low,mid-1, key); //在前半部分查找 else return BinSearch2(a,mid+1,high, key); //在后半部查找 }//inSearch2
§8.22有序表的折半检索 (二)判定树 ·折半检索判定树具有下列性质 ①任一结点的左右子树中的结点数目最多相差1 ②任意两棵折半检索判定树,若它们的结点数目相同,则它们的 结构完全等同(全等) ③具有n个结点的折半检索判定树的深度为「log2n」+1,即深度 与同结点数目的顺序二叉树相同。 ④折半检索判定树是平衡二叉树,即任一结点的左右子树的深度 最多相差1 ⑤折半检索判定树中任两个叶子所处层次号之差不超过1
25 §8.2.2 有序表的折半检索 (二)判定树 • 折半检索判定树具有下列性质： ①任一结点的左右子树中的结点数目最多相差1 ②任意两棵折半检索判定树，若它们的结点数目相同，则它们的 结构完全等同（全等） ③具有n个结点的折半检索判定树的深度为「log2 n」+1，即深度 与同结点数目的顺序二叉树相同。 ④折半检索判定树是平衡二叉树，即任一结点的左右子树的深度 最多相差1。 ⑤折半检索判定树中任两个叶子所处层次号之差不超过1