-
2021-02-28 15:03:44
折半查找介绍:
折半查找,找的是一个有序列表。理论就是先找中间的,如果中间数大于大于目标数,那么就只需要找上半份数据中再折半查找就可以了。一直到找到为止,不用遍历所有数据,效率很高。
实现折半查找的方法案例:package javalm;
public class biSearch {
/**
* @param args
*/
/*
折半查找--当查找表是有序表时,可采用折半查找;
基本思想:在有序表中,取中间元素作为比较对象,若给定值K与中间记录关键字相等,则查找成功;
若给定值K小于中间记录的关键字,则在表的左半区继续查找;
若给定值K大于中间记录的关键字,则在表的右半区继续查找,不断重复,直到查找成功/失败。
*/
//折半查找非递归算法
//查询成功返回该对象的下标序号,失败时返回-1。
int BiSearch(int r[],int n,int k)
{
int low=0;
int high=n-1;
while(low<=high)
{
int mid=(low+high)/2;
if(r[mid]==k)
return mid;
else
if(r[mid]
low=mid+1;
else
high=mid-1;
}
return -1;
}
//折半查找递归算法
//查询成功返回该对象的下标序号,失败时返回-1。
int BiSearch2(int r[],int low,int high,int k)
{
if(low>high)
return -1;
else
{
int mid=(low+high)/2;
if(r[mid]==k)
return mid;
else
if(r[mid]
return BiSearch2(r,mid+1,high,k);
else
return BiSearch2(r,low,mid-1,k);
}
}
public static void main(String[] args) {
biSearch bs=new biSearch();
int r[]={1,2,3,4,5};
System.out.println(bs.BiSearch(r,5,5));
System.out.println(bs.BiSearch2(r,1,5,5));
}
}
更多相关内容 -
java折半查找
2022-01-10 21:33:38java折半查找折半查找操作:使用折半查找有序数组中元素。找到返回索引(在数组中的位置),不存在输出-1。
分析:折半查找的前提是数组有序。
假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.
可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2.
(1)开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为mid>x,故应在前半段中查找。
(2)令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>mid,故确定应在后半段中查找。
(3)令新的front=mid+1=2,而end=2不变,则新mid=2,此时a[mid]=x,查找成功。
(4)如要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。import java.util.Scanner; public class SuZu4 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int[] a = {3, 12, 24, 36, 55, 68, 75, 88}; System.out.print("请输入要查找的数:"); int n =sc.nextInt(); int front = 0; int end = a.length - 1; int mid = (front + end) / 2; do { int jg; if (a[mid] > n) { end = mid - 1; mid = (front + end) / 2; if (end < front) { System.out.println("查找不成功"); return; } } else if (n > a[mid]) { front = mid + 1; mid = (front + end) / 2; if (front > end) { System.out.println("查找不成功"); return; } } } while (a[mid] != n); System.out.println(mid); } }
折半查找递归操作
import java.util.Scanner; public class SuZu62 { public static void main(String[] args) { int[] a = {3, 12, 24, 36, 55, 68, 75, 88}; Scanner sc = new Scanner(System.in); System.out.print("请输入要查找的数:"); int n = sc.nextInt(); int s = seek(a, 0, a.length - 1, n); System.out.println(s); } public static int seek(int[] arr, int front, int end, int n) { int mid = (end + front) / 2; if (front <= end) { if (arr[mid] == n) { return mid; } else if (arr[mid] > n) { return seek(arr, front, mid - 1, n); } else { return seek(arr, mid + 1, end, n); } } else { return -1; } } }
结果如上
-
java实现折半查找算法
2019-12-06 17:27:55所谓的二分查找,指的是将待查的数据序列而分化,然后对比中间中间值和要查找值,判断结果,相等则找到,小于则在左边的子序列找,大于则在右边的子序列找 -
java折半查找法
2021-03-16 20:16:24折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=1,上限为h=5,求中点m=(l+h)/2,用X与中点元素am比较,若X等于...折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X,其基本思想是: 设查找数据的范围下限为l=1,上限为h=5,求中点m=(l+h)/2,用X与中点元素am比较,若X等于am,即找到,停止查找;否则,若X大于am,替换下限l=m+1,到下半段继续查找;若X小于am,换上限h=m-1,到上半段继续查找;如此重复前面的过程直到找到或者l>h为止。如果l>h,说明没有此数,打印找不到信息,程序结束。
方法一:
package suanfa;
import java.util.*;
public class zheban {
public static void main(String[]args)
{
int[]a={1,3,6,8,9,89,765};
int time=search(a,8);
System.out.println(time);
}
public static int search(int[]a,int key)
{
int low=1;
int high=a.length;
int mid;
while(low
{
mid=(low+high)/2;
if(key==a[mid-1])
return mid-1;
else if(key>a[mid-1])
low=mid+1;
else
high=mid-1;
}
return 0;
}
}
方法二:
package m;
import java.util.*;
public class zheban {
public static int[]data={1,3,5,7,9,11,22,44,67,89};
public static void main(String[]args)
{
System.out.println("please enter the data you will find:");
Scanner scan=new Scanner(System.in);
int key=scan.nextInt();
zheban(key,0,9);
}
public static boolean zheban(int key,int low,int high)
{
int l=low;
int h=high;
int mid;
while(l
{
mid=(l+h)/2;
if(data[mid]==key)
{
System.out.println("find "+"the data is in array "+(mid+1));
return true;
}
else if(key
h=mid-1;
else if(key>data[mid])
l=mid+1;
}
System.out.println("failed");
return false;
}
}
-
java折半查找算法
2021-04-17 02:47:29high 时表示查找区间为空,查找失败 } Java 代码: /** * 二分查找算法 * * @param srcArray 有序数组 * @param target 被查找的元素 * @retur......6 、不断利用循环和折半查找算法查找一个整数 n 是否在一个无序的 ...//当 low>high 时表示查找区间为空,查找失败 } Java 代码: /** * 二分查找算法 * * @param srcArray 有序数组 * @param target 被查找的元素 * @retur......
6 、不断利用循环和折半查找算法查找一个整数 n 是否在一个无序的 int 型数...
查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,文中介绍四种查找算法,分别是顺序查找、二分查找、二叉排序树查找和哈希查找。...
. 6.编写基于Java语言的折半查找算法。 /*** * 功能:该算法实现折半...
. 6.编写基于Java语言的折半查找算法。 /*** * 功能:该算法实现折半...
3)利用排序算法将一数组按由小到大排列,输入一个数据,查找在数组中是否存在,采用“折半查 找”加快查找速度。 所谓“折半查找”就是先与中间位置元素进行比较,......
第八章查找补充作业解答(Java版)_理学_高等教育_教育专区。O(∩_∩)O~ 第八章查找 作业解答 作业解答 1.画出对长度为 10 的有序表进行折半查找的判定树,......
3)利用排序算法将一数组按由小到大排列,输入一个数据,查找在数组中是否存在,采用“折半查 找”加快查找速度。 所谓“折半查找”就是先与中间位置元素进行比较,......
Java程序设计大学教程 第五章 算法与数据结构程序是建立在数据结构基础上使用计算机 语言描述的算法,因此简单地讲,程序也 可以表示成:算法+数据结构。 本章介绍算法......
六、 实验体会 本次试验解决了二分查找和三分查找的问题,加深了对分治法的 2015-2016 学年 第一学期 算法设计与分析实验报告 理解,收获很大,同时我也理解到......
上传第9章查找习题,二分法查找例题,写出二分查找算法vb,数据结构查找习题,二分法查找c语言,查找习题,数据结构(查找习题),java二分法查找算法,数据结构查找的习题,二分......
(2)题意 将顺序、折半查找算法设计成线程,启动二个不同 线程同时运行,并计算不...
public static int binarySearch(int[] table, int value) //折半查找算法,数组元素已按升序排列 { //若查找成功返回元素下标,否则返回-1 if (table!=null)......
共 5 if(adj.edges[i][k]==1 && visited[k]==0) { visited[k]=1; connected(adj,k,j,c); } else k++; } } 8.写出实现折半查找的算法或程序......
//当 low>high 时表示查找区间为空,查找失败 } Java 代码: /** * 二分查找算法 * * @param srcArray 有序数组 * @param target 被查找的元素 * @retur......
2、有序表的查找问题描述折半查找也称为二分查找,作为二分查找对象的数据必须是顺序...
("哈希表开放地址法的查找")) { ... } //退出 if (command.equals("退出")) System.exit(0); } 四、算法设计 我负责的是按钮动作的实现。 1、流程图......
public static int binarySearch(int[] table, int value) { //折半查找算法,数组元素已按升序排列 //若查找成功返回元素下标,否则返回-1 if (table!=null)......
? 熟悉数组的排序、查找等算法。 ? 掌握字符数组的使用方法。 实验内容: 1) 编写数组的排序程序。 2) 编写折半查找的程序。 3) 编程实现:产生一个 1-12 ......
8.查找 ① 理解查找的基本概念和查找算法效率的分析方法。 ② 掌握线性表的顺序查找、有序顺序表的折半查找、索引顺序表的分块查找算法。 ③ 理解散列表的概念,......
-
java 折半查找法(二分查找)实例
2020-09-05 13:52:53java 折半查找法(二分查找)实例,需要的朋友可以参考一下 -
Java折半查找+API+一些方法
2020-11-08 09:14:56大纲 一、折半查找 二、API 三、API的一些方法 -
JAVA 折半查找 实验代码
2014-01-10 22:01:12JAVA 数据结构二分法查找代码。(实验) -
java折半查找算法实现
2020-11-05 09:12:13折半查找算法: public class hacker_01_zheban { public static void main(String[] args) { int[] arr= {12,10,7,6,2,100}; kuaipai(arr,0,arr.length-1); // 参考我的java快速排序算法 for (int i : arr)... -
Java 折半查找法(二分法) 【小案例详解】
2019-01-17 21:32:31折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4,要查找的数是X, 其基本思想是: 设查找数据的范围下限为l=0,上限为h=4,求中点m=(l+h)/2,用X与中点元素am比较,若X... -
java 折半查找
2021-03-07 14:33:05public static void main(String[] args) {int[] arr = {0,1,2,3,4,5,6,7,8,9,10};System.out.println(halfSearch_2(arr,5));}public static int halfSearch_1(int[] arr,int key){int min = 0,max = arr.length-1,m... -
java折半查找/二分法查找
2021-10-14 17:24:13public class ArraySearch { public static void main(String[] args) { // 数组元素第二种查找方法(二分查找法/折半查找) int[] 数组名={2,6,8,9,100}; Scanner sc=new Scanner(System.in); System.out.print(... -
Java 折半查找,普通查找的练习
2015-03-15 16:36:07这是一个关于数组查找方式的练习,供大家学习交流~~ -
java折半查找法的两种方式
2021-03-07 14:33:06} //折半的第二种方式 public static int halfSerach_2(int[] arr,int key){ int min = 0,max = arr.length-1,mid; while(min){ mid = (max+min)>>1; if (key>arr[mid]) { min = mid+ 1; }else if(keyarr[mid]) { ... -
Java折半查找(二分法)
2021-03-04 16:34:20折半查找 将数组一分为二 之后比较查找哈 输入一个数 查找这个数在数组中位于哪个位置 并将下标返回 方法: 将数组操作成升序(降序也可以哈 这个案例是升序的方法哈) 然后分成左右2半 将需要查找得数与左右2半数组... -
Java 折半查找
2017-03-05 11:06:02public class BanSearch { //折半查找必须是有序数组 public static void main(String [] args) { int [] arr = {2,5,33,58,76}; int index = halfSearch(arr,58); System.out.println("index = "+index); int... -
java实现折半查找
2021-02-12 14:35:04} } O(1):直接寻址到 O(n):遍历n个元素 O(logn):随着元素增加,呈现指数关系 O(n2):增加一倍元素,时间增加4倍 折半查找的算法时间复杂度最好的情况是O(1),平均情况下是logn。 分析一下,折半查找的... -
Java实现折半查找(二分查找)
2022-01-11 09:05:46对一组有序序列进行二分查找,找到元素并输出其索引下标,反之则查找失败 -
Java 递归和折半查找
2021-03-02 16:02:24折半查找 折半查找又称为二分查找,这种查找方法需要待查的查找表满足两个条件: 首先,查找表必须使用顺序存储结构; 其次,查找表必须按关键字大小有序排列。 key=21的查找过程 key=85的查找过程 ❤️ 非递归的... -
Java查找算法之折半查找
2022-03-25 19:48:22第1关:折半查找(二分查找) 本关任务:给定一个排好序的数组,然后输入另一个整数,判断该整数在数组中的什么位置,返回该整数第一次出现的位置(位置从0开始),否则返回-1。 package step1; public class Task ... -
Java折半查找算法
2020-05-31 21:10:44折半查找 import java.util.Arrays; /** * 折半查找 */ public class Test2 { public static void main(String[] args) { long[] longs1={25,21,41,58,45,78,89,56,25,12,23,14}; Arrays.sort(longs1); System... -
Java算法之折半查找法
2020-04-26 10:43:49Java 算法之折半查找法 算法介绍 折半查找法要求线性表是有序的,即表中记录按关键字有序(假设是递增有序的)。 折半查找的基本思路:设 R[low, ···, high] 是当前的查找区间,首先确定该区间的中间位置 mid = ... -
Java中折半查找法
2019-03-09 17:07:08首先,Java的折半查找法适用于有序数组中某一元素下标的查找。例如: //折半查找 public class halfSerach { public static void main(String[] args) { int[] a = {12,23,34,36,47,108}; int index = ... -
java 查找算法(折半查找算法)
2021-03-02 15:20:26// 折半查找 public static void main(String[] args) { int[] arr = {2,6,3,1,8,9,10}; int index = binarySearch(arr,8); System.out.print(index);//输出 4 } /** * * @param arr 要进行查找的数组...