国内十个免费自学网站,wordpress 获取id,wordpress挖,潍坊+网站建设一、前言#xff1a; 这是怀化学院的#xff1a;Java数据结构中的一道难度中等的一道编程题(此方法为博主自己研究#xff0c;问题基本解决#xff0c;若有bug欢迎下方评论提出意见#xff0c;我会第一时间改进代码#xff0c;谢谢#xff01;) 后面其他编程题只要我写完… 一、前言 这是怀化学院的Java数据结构中的一道难度中等的一道编程题(此方法为博主自己研究问题基本解决若有bug欢迎下方评论提出意见我会第一时间改进代码谢谢) 后面其他编程题只要我写完并成功实现会陆续更新记得三连哈哈! 所有答案供参考不是标准答案是博主自己研究的写法。(这一个题书上也有现成的代码重要的是理解它的算法原理!) 二、题目要求 (第 13 题) 折半查找(难度系数75) 折半查找 标准输入输出 题目描述 实现折半查找。要求查找给定的值在数据表中相应的存储位置。本题目假定输入元素均按非降序输入。 输入 输入包含若干个测试用例第一行为测试用例个数k。每个测试用例占3行其中第一行为元素个数n第二行为n个元素值即数据表中的元素第三行为需要查找的元素。 输出 对每一测试用例分别用一行输出两个值分别表示相应的位置和查找次数用空格隔开。如果查找不成功则位置表0表示。 输入样例 1 5 1 2 4 7 9 4 输出样例 3 1 三、代码实现 (代码的做题原理全部在代码注释中若还有疑问也可以翻书关于折半查找的内容)
(1)创建一个折半查找的类里面关有折半查找的操作方法与一个计查找总次数的成员变量 补充(考试的时候不用这么麻烦直接在一个类的主方法里写完所有操作细节就行这里我这样写是为了方便读者理解) package com.fs.search;public class Bin_Search {private int number;public Bin_Search(){this.number0; //赋初始值}public int getNumber(){return number;}public int binSearch(int[]data,int value){int low0; //最开始的最小索引int highdata.length-1; //最开始的最大索引位置int mid; //折半值while(highlow){ //只要满足最大索引不小于最小索引那就是还没查找完number;mid(lowhigh)/2;if(data[mid]value){return mid;}else if(data[mid]value){lowmid1; //如果不相等那么如果这个位置的数小于要查的值那么要查的数只有可能会在比mid大的那一半块区间里出现所以之前小的下标往后移}else if(data[mid]value){highmid-1; //如果不相等那么如果这个位置的数大于要查的值那么要查的数只有可能会在比mid小的那一半块区间里出现所以之前大的下标往前移}//继续循环找}return -1; //如果没查到表示位置输出0。那边加1就是0了}
}(2)测试类满足题目的所有输入需求
package com.fs.search;
import java.util.Arrays;
import java.util.Scanner;
public class Test_Bin_Search {public static void main(String[] args) {Scanner sc new Scanner(System.in);int k sc.nextInt(); //需要测试的总次数while(k0){int n sc.nextInt(); //每次测试的元素个数int[] data new int[n];for(int i0;in;i){data[i]sc.nextInt();}//考试不加这个也没啥事因为它后台测试肯定是升序的数值构成的数值(不过为了我们的方便)Arrays.sort(data); //加上这个就是为了满足题目测试查找的数组永远都是升序排序的这样可以随便输入啥数组都能进行查找了int valuesc.nextInt(); //需要查找的值Bin_Search b new Bin_Search();int indexb.binSearch(data,value)1; //对象调用方法System.out.print(index b.getNumber());k--;}}
}
四、不同情况的代码测试运行结果
1首先是题目中的测试输入样例(最好手打输入测试直接复制可能格式问题导致报错) 2 测试2个测试样例(最好手打输入测试直接复制可能格式问题导致报错) 35 1 5 8 9 12 12 4 2 4 6 8 2 5 1 3 7 16 85 2 代码运行结果
