2、二分查找（又称折半香找）（1)算法的基本思想：先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至前半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。思考题：问：能否使用单链表结构进行折半查找？无法实现！因全部元素的定位只能从头指针head开始
(1)算法的基本思想：先给数据排序（例如按升序排好），形成 有序表，然后再将key与正中元素相比，若key小，则缩小至 前半部内查找；再取其中值比较，每次缩小1/2的范围，直到 查找成功或失败为止。 思考题： 问：能否使用单链表结构进行折半查找？ ——无法实现！因全部元素的定位只能从头指针head开 始 2、二分查找（又称折半查找）
折半查找举例：已知如下11个元素的有序表：（0513192137566475808892）.请查找关键字为21的数据元素的查找思路。high指向待查元素所Low指向待查元mid指向待查元素所在在区间的上界素所在区间的下区间的中间位置界解：①先设定3个辅助标志：low,high,mid，显然有 : mid= (low+high)/2运算步骤：2（1）low=0,high=10，故mid=5，待查范围是[0,10](2）若a[mid]<key，说明keye［mid+1,high]则令：1ow=mid+1;重算mid=L(low+high)/2』;(3）若a[mid]>key，说明keye[low，mid-1]，则令：high=mid-1;重算mid；(4)若a［mid］==key，说明查找成功，元素序号=mid;（1）查找成功：a[mid]=key结束条件：（2）查找不成功：high<low（意即区间长度小于0）
② 运算步骤： (1) low =0,high =10 ,故mid =5 ，待查范围是 [0,10]； (2) 若 a[mid] < key，说明 key[ mid+1,high] ， 则令：low =mid+1;重算 mid＝ (low+high)/2；. (3) 若 a[mid]> key，说明key[low ,mid-1]， 则令：high =mid–1;重算 mid ； (4)若 a[ mid ]= = key，说明查找成功，元素序号=mid; 结束条件：（1）查找成功 ： a[mid]= key （2）查找不成功 ： high<low （意即区间长度小于0） 解：① 先设定3个辅助标志:low,high,mid， 折半查找举例： Low指向待查元 素所在区间的下 界 high指向待查元素所 在区间的上界 mid指向待查元素所在 区间的中间位置 显然有：mid= (low+high)/2 已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 的数据元素的查找思路
二分查找递归算法public static int biSearch(int a, int elem, int low, int high)int mid;//查找不成功if(low> high) return -1;mid = (low + high) / 2;//查找成功if(elem=-= a|midD) return mid;else if(a[mid]> elem)//在上半区查找return biSearch(a,elem,low,mid-1)elsereturnbiSearch(a,elem,mid+1,high)；//在下半区查找
public static int biSearch(int[] a, int elem, int low, int high){ int mid; if(low > high) return -1; //查找不成功 mid = (low + high) / 2; if(elem == a[mid]) return mid; //查找成功 else if(a[mid] > elem) return biSearch(a, elem, low, mid - 1); //在上半区查找 else return biSearch(a, elem, mid + 1, high); //在下半区查找 } 二分查找递归算法
二分查找非递归算法：public static int biSearch(int a, int elem)int n = a.Length;int low= 0, high = n - 1, mid;while(low<- high)(mid = (low + high)/2;if(a[mid] == elem) return mid;else if(a[mid]< elem) low = mid + 1;else high = mid - 1;1return -1;
二分查找非递归算法： public static int biSearch(int[] a, int elem){ int n = a.Length; int low = 0, high = n - 1, mid; while(low <= high){ mid = (low + high)/2; if(a[mid] == elem) return mid; else if(a[mid] < elem) low = mid + 1; else high = mid - 1; } return -1; }
可以用查找二叉树/判定树来分析ASL以 (a1, a2, a3, a4, as, ae, ar, ag, ag, a10, a) 为例:a6判定树由表中元素个数决aoa3定，具n个元素表的折半查找判定树是唯一的，a1aa4aa2asagaii找到有序表中任一记录的过程就是：走了一条从根结点到与该记录对应结点的路径。比较的关键字个数为：该结点在判定树上的层次数（设根结点所在层数为1)。查找成功时比较的关键字个数最多不超过树的深度d
• 找到有序表中任一记录的过程就是：走了一条从根结点到与该记 录对应结点的路径。 • 比较的关键字个数为：该结点在判定树上的层次数(设根结点所在 层数为1)。 • 查找成功时比较的关键字个数最多不超过树的深度 d 。 可以用查找二叉树/判定树来分析ASL 以（a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 , a10, a11）为例： a6 a3 a9 判定树由表中元素个数决 定，且n个元素表的折半 a 查找判定树是唯一的。 1 a4 a7 a10 a2 a5 a8 a11