数据结构和算法是一个程序的灵魂,优化程序的主要手段。在查询里,分为静态查询和动态查询。有序表是静态查询的一种,在。有序表查找过程中,可以用折半查找实现。代码如下:
Java代码
package Array;
/**
* 折半查找
* @author luozhong
*
*/
public class ArrayTest_lesson1 {
//定义数组
int array[]=new int[]{0,1,2,3,4,5,6,7,8,9};
//定义三个变量
int low, mid,high;
public static void main(String args[]){
new ArrayTest_lesson1().init(9);
}
public void init(int temp){
//此变量指着第一个元素
low=1;
//此变量指着末元素
high=array.length;
//调用查询方法
int key=Index(low,high,temp);
System.out.println("查询结果为:"+key);
}
private int Index(int low2, int high2, int temp) {
//判断循环的条件
while(low2<=high2){
mid=(low2+high2)/2;
//判断是否与查询值相等,返回索引位置
if(temp==array[mid]) return mid;
//如果小于数组元素
else if(temp<array[mid]) high2=mid-1;
////如果大于数组元素
else low2=mid+1;
}
return 0;
}
}
折半查找的性能分析,他查找的过程可用二叉树来描述。折半查找在查找不成功时候和给定值进行比较关键字个数最多也不超过{logn/log2}+1.
假设表中每个记录查找概率相等(p=1/n),则查找成功时的折半查找的平均查找长度如图:
分享到:
相关推荐
5. **查询优化**:除了基本的散列查找外,可能还会涉及到二分查找、Trie树等数据结构的结合,以进一步提升查询速度。例如,如果电话号码的区号固定且较短,可以考虑先用区号进行预筛选,再用剩余部分进行哈希。 6. ...
书中会涵盖各种算法,如排序算法(冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等)、搜索算法(线性搜索、二分搜索、深度优先搜索、广度优先搜索)以及动态规划、贪心算法和回溯法等。这些算法不仅...
Java数据结构和算法中文这本书作为学习资料,涵盖了Java语言中数据结构和算法的重要知识点。在介绍数据结构和算法之前,我们先了解下什么是数据结构和算法,以及它们在程序设计中的重要性。 数据结构是一门研究组织...
- **搜索算法**:线性搜索、二分搜索、深度优先搜索(DFS)、广度优先搜索(BFS)。 - **图遍历算法**:深度优先搜索(DFS)和广度优先搜索(BFS)在图结构中的应用。 - **动态规划**:解决最优化问题,如背包...
常见的算法有排序算法(如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序)、查找算法(如线性搜索、二分查找)、图算法(如深度优先搜索、广度优先搜索)、树算法(如二叉搜索树、平衡树AVL和红黑树)...
- **图**:用于表示节点之间的关系,Java中并没有内置的图数据结构,但可以通过自定义类实现。 2. **算法**: - **排序算法**:冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,不同的排序算法有...
数据结构是计算机科学中的核心概念,它涉及到如何有效地组织和管理数据,以便于高效地进行存储、检索...通过学习这本书,你可以深入了解Java中如何实现和应用各种数据结构,提升编程能力,为解决实际问题打下坚实基础。
以上只是Java数据结构和算法的一部分内容,深入学习还包括算法的时间复杂度分析、记忆化搜索、并查集、字典树(Trie)、图的遍历算法(深度优先搜索和广度优先搜索)等。理解并熟练应用这些知识点对于提升Java编程...
第28题可能要求实现一个高效的搜索功能,如二分查找,或者是在链表、数组等数据结构上进行操作。 2. Exercise05_29.class:这可能涉及到数据结构的复杂性分析,例如时间复杂度和空间复杂度的计算,或者实现一种平衡...
《2018JAVA经典教程:数据结构与算法经典问题解析》是一本深入探讨Java语言中数据结构和算法实现的教程。这本书旨在帮助读者理解并掌握如何使用Java有效地设计和解决各种计算问题。数据结构是计算机科学的基础,而算...
《Java版数据结构与算法》是一份专注于Java编程语言实现的数据结构和算法的学习资源。这份压缩包中的"ljg_resource1"可能是一个包含各种代码示例、教程文档或者练习题的文件,旨在帮助学习者深入理解和掌握数据结构...
在阅读《Java数据结构和算法》(第二版)的过程中,读者不仅可以深入理解各种数据结构和算法的工作原理,还能通过实例学习如何在Java中实现它们,从而提升编程技巧和解决实际问题的能力。这本书对于那些寻求进阶的...
在Java中,可以使用ArrayList或者LinkedList等内置数据结构作为基础,但为了保持排序,ArrayList可能更为适合,因为它支持O(n)时间复杂度的插入和删除操作,而LinkedList虽然插入和删除操作更快,但在查找时效率较低...
在Java中,`java.util`包提供了许多预定义的数据结构,如ArrayList、LinkedList、Stack、Queue、HashSet和HashMap等。例如,ArrayList使用动态数组实现,适合快速的随机访问;而LinkedList则基于双向链表,插入和...
在Java中,数据结构主要包括以下几种: 1. 数组:最基础的数据结构,用于存储固定大小的同类型元素集合。数组提供了快速访问和直接修改元素的能力,但插入和删除元素效率较低。 2. 链表:链表中的元素在内存中不是...