二、折半查找(Binary Search). 1、是对有序表的一种效率较高的线性查找，也称二 分法查找； 2、用此方法，表中的记录必须是按关键字递增（减 ) 的次序顺序排列，且为顺序存储结构。 3、实质：先确定待查记录所在的区间，然后逐渐缩小 范围直至得到查找结果为止；
二、折半查找（Binary Search） 1、 是对有序表的一种效率较高的线性查找，也称二 分法查找； 2、 用此方法，表中的记录必须是按关键字递增（减 ） 的次序顺序排列，且为顺序存储结构。 3、实质：先确定待查记录所在的区间，然后逐渐缩小 范围直至得到查找结果为止；
4、假设Iow和high分别指向待查记录所在范围的下界和上界， 指针mid指示区间的中间位置，即 low的初值为1，high的初值为有序表的长度
4、假设low和high分别指向待查记录所在范围的下界和上界， 指针mid指示区间的中间位置，即 low的初值为1，high的初值为有序表的长度。 2 low high mid + =
0 2345678910111213 21 74813291B538246952 给定的k值 low-1 mid=7 21 high=13 owd-21 high=6 1ow-4 high=6 mid=521 low-4 high-4 查我成奶 返回位置4 mid=4 21
21 7 14 18 21 23 29 31 35 38 42 46 49 52 0 1 2 3 4 5 6 7 8 9 10 11 12 13 给定的k值 low=1 mid=7 high=13 21 high=6 low=1 mid=3 21 low=4 high=6 mid=5 21 low=4 high=4 mid=4 21 查找成功 返回位置4
012345678910111213 407481329B13538246492 给定的k值 low=1 mid-740 high=13 low=8 mid=10 high=13 40 low=8 high=9 mid=840 ■Bns■■■■s自gsg■目gs■■■ss指■■■s■MMaEnn目MmEm■ss■sss■sg■日■■■ss■■s■sggg8ss■g low=9 high=9 mid=9 40 high=9 low=10 查找不或功 返回位置0 【low>high】
40 7 14 18 21 23 29 31 35 38 42 46 49 52 0 1 2 3 4 5 6 7 8 9 10 11 12 13 给定的k值 low=1 mid=7 40 high=13 high=9 low=8 mid=10 40 low=8 high=13 mid=8 40 查找不成功 返回位置0 low=9 high=9 mid=9 40 high=9 low=10 【low>high】
int BinSearch(SqTable tb1,ElemType k) int mid,flag=0; low=1;high=length; while(low<=high) mid=(low+high)/2; if(k<tb1.elem[mid].key)high=mid-1; else if(k>tb1.elem[mid].key)low=mid+1; else flag=mid;break; return flag; }
int BinSearch(SqTable tb1,ElemType k) { int mid,flag=0; low=1; high=length; while(low<=high) { mid=(low+high)/2; if(k<tb1.elem[mid].key) high=mid-1; else if(k>tb1.elem[mid].key) low=mid+1; else { flag=mid; break;} } return flag; }