20172319 2018.10.12 《Java程序设计教程》第6周课堂测验
- 课程:《程序设计与数据结构》
- 班级：1723
- 学生：唐才铭
- 学号：20172319
- 指导老师：王志强
- 日期：2018.10.12
- 必修/选修：必修
目录
- 测试内容
- 测试要求
- 实验步骤
- 需求分析
- 代码实现及解释
- 程序运行结果及代码截图
- 测试过程及遇到的问题
- 代码链接
- 参考资料
测试内容
- 已知线性表具有元素{5,13,19，21,37,56,64,75,80,88,92}，如果使用折半查找法，ASL是多少？
（本题目2分，要求写出结题过程）
测试要求
- 完成蓝墨云班课上的ASL测试任务；并截图（类代码，测试代码，运行结果代码）发送至蓝墨云
- 托管代码至git@OSC，详情参考使用开源中国托管代码
- 返回目录
实验步骤
需求分析
- 需要了解、掌握与折半查找相关的知识
- 了解ASL是什么？
代码实现及解释
折半查找（二分查找）：
- 相对于线性查找来说效率较高；
- 要求：被查找元素处在一个项目组中；被查找的元素已经排好顺序；
- 原理：首先先确定在该存储结构的中点位置；之后将待查找的值与中值进行比较；若二者相等，则查找成功并返回此位置，否则确定新的查找区间，再继续进行二分查找：
- 1.若待查找值大于中值，则新的查找区间为前一查找区间的中值及区间后半部分元素。
- 2.若待查找值小于中值，则新的查找区间为前一查找区间的中值及区间前半部分元素。
- 从初始的查找区间开始，每经过一次与当前查找区间的中点位置上的结点值的比较，即可判断查找是否成功，不成功则当前的查找区间便缩小一半。这一过程一直重复，直至找到待查找值的位置，或者直至当前的查找区间为空（即查找失败）为止。
public class BinarySearch {
/*
* 循环实现二分查找算法arr 已排好序的数组x 需要查找的数-1 无法查到数据
*/
public static int binarySearch(int[] arr, int x) {
int low = 0;
int high = arr.length-1;
while(low <= high) {
int middle = (low + high)/2;
if(x == arr[middle]) {
return middle;
}else if(x <arr[middle]) {
high = middle - 1;
}else {
low = middle + 1;
}
}
return -1;
}
//递归实现二分查找
public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){
int midIndex = (beginIndex+endIndex)/2;
if(data <dataset[beginIndex]||data>dataset[endIndex]||beginIndex>endIndex){
return -1;
}
if(data <dataset[midIndex]){
return binarySearch(dataset,data,beginIndex,midIndex-1);
}else if(data>dataset[midIndex]){
return binarySearch(dataset,data,midIndex+1,endIndex);
}else {
return midIndex;
}
}
public static void main(String[] args) {
int[] arr = { 6, 12, 33, 87, 90, 97, 108, 561 };
System.out.println("循环查找：" + (binarySearch(arr, 87) + 1));
System.out.println("递归查找"+binarySearch(arr,3,87,arr.length-1));
}
}
ASL（Average Search Length ：平均查找长度）
衡量查找效率的一个标准。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=∑PiCi (i=1,2,3,…,n)。其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数，∑Pi=1。
程序运行结果及代码截图
已知线性表具有元素{5,13,19，21,37,56,64,75,80,88,92}，如果使用折半查找法，ASL是多少？
解答：
表*有11个元素，其中56为表中间元素的值。
使用二分查找，则：
56需要查找1次；
19及80需要查找2次；
13，21，75，88需要查找3次；
5，37，64，92需要查找4次；
查找的概率相等：1/11;
ASL=1/n * ∑Ci = 1/11 * (1 + 2 * 2 + 4 * 3 + 4 * 4) = 33/11 = 3