数组是应用最广泛的数据结构，也是最简单的数据结构，它有着结构简单，算法通俗易懂的优点。数组又分为有序数组和无序数组，我们通常用的都是无序数组。下面是这两种数组之间的区别
无序数组的优点：插入快，根据索引查找快。缺点：在未知数组位置的情况下查找慢，删除慢。
有序数组的优点：使用二分法查找快。缺点：插入数据和删除数据慢。因为插入数据要做排序操作。
综合以上，可以看出他们各自的使用场景，无序数组适合经常做插入操作和用索引访问的环境，而有序数组更趋向于随机查找。
下面是封装的一个数组类，扩展了了insert,delete,find方法,有许多不足之处，比如insert方法没有判断数组界限。懒得搞了。
package ArrayDemo;
public class HighArray {
private int[] arr = null;
private int nElement = 0;//当前数组的实际长度
public HighArray(int size){
this.arr = new int[size];
this.nElement = 0;
}
/**查找指定元素是否在数组中存在，返回结果
* @param c
* @return
*/
public boolean find(int c){
int i;
for ( i = 0; i < nElement && arr[i]!=c; i++);
return i != nElement;
}
/**插入
* @param c
*/
public void insert(int c){
arr[nElement++] = c;
}
/**删除
* @param c
* @return
*/
public boolean delete(int c){
int i;
for ( i = 0; i < nElement && arr[i]!=c; i++);
if(i!=nElement){
nElement--;
for (int j = i; j < nElement; j++) {
arr[j] = arr[j+1];
}
return true;
}else{
return false;
}
}
/**获取当前最大元素
* @return
*/
public int getMax(){
if(nElement > 0){
int max = arr[0];
for (int i = 1; i < nElement; i++) {
if(arr[i] > max)max = arr[i];
}
return max;
}
return -1;
}
/**删除并且返回最大元素
* @return
*/
public int removeMax(){
if(nElement > 0){
int max = arr[0];
for (int i = 1; i < nElement; i++) {
if(arr[i] > max)max = arr[i];
}
delete(max);
return max;
}
return -1;
}
public void display(){
for (int i = 0; i <nElement; i++) {
System.out.println(arr[i]);
}
}
/**
* 删除数组中存在的重复元素并缩小数组长度
*/
public void noDup(){
int count = 0;
for (int i = 0; i < nElement; i++) {
if(arr[i] != -1){// -1为空值的表现
for (int j = 0; j < nElement; j++) {
if(i!=j && arr[i] == arr[j]){
arr[j] = -1;
count++;
}
}
}
}
if(count > 0){
int j = 0;
for (int i = 0; i < nElement; i++) {
if(arr[i]!=-1){
arr[j++] = arr[i];
}
}
for (int k = j; k < nElement; k++) {
arr[k] = 0;
}
}
nElement-=count;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
HighArray h = new HighArray(100);
h.insert(7);
h.insert(74);
h.insert(74);
h.insert(74);
h.insert(89);
h.insert(12);
h.insert(8);
h.noDup();
h.display();
// h.delete(12);
}
}
上面是对一个无序数组做了一些封装和扩展。实现起来稍微简单点。下面介绍下有序数组的二分查找法。
要实现二分查找法数组必须先满足两个条件1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
二分查找法的基本原理就是：逐渐缩小查询范围，直到查找到元素或者查找不到此元素。它的优点是查找次数较线性查找（也就是按顺序查找所有元素）要高，而且当数组越大时查找次数的优势较线性查找越明显。下面是它查找不同数据量所需要的次数
怎么样，是不是数据量越大查找次数的优势就越大，比如在10000里查找一个元素，线性查找需要的平均次数是1000/2 = 5000次， 而二分查找法的计算公式是以二为基数的对数 ，所谓对数就是指数的反函数 ，一般计算器的log函数就是以10为基数的对数，那么计算10000的二分查找法所需次数的公式就是log(10000) * 3.322 ，乘以3.322是因为要将该结果从10的基数转换成2的基数，这样下来四舍五入差不多就是所需次数了。结果是 13.288 取整就是14次。5000比14可想而知效率高了多少。ps:也可以这样计算log2(x) = log(x) / log(2)
下面是二分法查找的基本步骤（假如是数组元素升序排序的）
1.将需查找元素和数组中间的元素比较，如果相等则返回，如果数组中间元素比需查找元素大则说明目标元素的位置在中间元素的前面，反之在后面。
2.通过步骤1，已经缩小了一半的范围，然后重复步骤1，直到找到元素或者找不到元素为止，就算找不到也最多就是查找Math.ceil(log(数据长度）* 3.322 )次。
这有点象我们平常的猜数游戏
java代码二分法实现
public int bianrySearch(int[] arr,int searchKey){
int lowerBound = 0, upperBound = arr.length - 1;
while(lowerBound <= upperBound){
int curIn = (lowerBound + upperBound)/2;
if(arr[curIn] == searchKey){
return curIn;
}else if(arr[curIn] > searchKey){
upperBound = curIn - 1;
}else{
lowerBound = curIn + 1;
}
}
return src.length;
}
看的不是很懂？没关系，看下面一张图您可能就明白了。
就是二分法这样逐渐缩小查询范围的原理来实现的。
下面是一个用二分法实现了find,delete,insert方法的数组类
package ArrayDemo;
public class OrderArray {
private int[] arr = null;
private int nElement = 0;
public OrderArray(int size){
this.arr = new int[size];
this.nElement = 0;
}
public int find(int c){
int lowerBound = 0, upperBound = nElement - 1;
while(lowerBound <= upperBound){
int middle = (lowerBound + upperBound)/2;
if(arr[middle] == c){
return middle;
}else if(arr[middle] > c){
upperBound = middle - 1;
}else{
lowerBound = middle + 1;
}
}
return nElement;
}
private int doSearchRecursive(int lower,int upper,int c){
while(lower <= upper){
int middle = (lower + upper)/2;
if(arr[middle]==c){
return middle;
}else if(arr[middle] < c){
return doSearchRecursive(middle + 1, upper, c);
}else{
return doSearchRecursive(lower, middle -1, c);
}
}
return nElement;
}
/**二分法递归实现
* @param c
* @return
*/
public int findRecursive(int c){
return doSearchRecursive(0,arr.length - 1,c);
}
public void insert(int c){
int lowerBound = 0,upperBound = nElement -1,max = nElement;
while(lowerBound <= upperBound ){//用二分法查找在数组中第一个比c大的元素
int middle = (lowerBound + upperBound)/2;
if(arr[middle] == c){
max = middle;
break;
}else if(arr[middle] > c){
max = middle;
upperBound = middle - 1;
}else{
lowerBound = middle + 1;
}
}
//移动数组
for (int i = nElement; i > max; i--) {
arr[i] = arr[i - 1];
}
arr[max] = c;
nElement++;
}
/**将两个有序的数组合并成一个有序的数组
* @param src1
* @param src2
*/
public void mearge(int[] src1,int[] src2){
int[] tar = new int[src1.length + src2.length];
for (int i = 0,k=0,j=0; i < tar.length; i++) {
if(j >= src2.length || (k < src1.length && src1[k] < src2[j])){
tar[i] = src1[k++];
}else{
tar[i] = src2[j++];
}
}
for (int i = 0; i < tar.length; i++) {
System.out.println(tar[i]);
}
}
public boolean delete(int c){
int index = find(c);
if(index != nElement--){
for (int i = index; i < nElement; i++) {
arr[i] = arr[i + 1];
}
return true;
}else{
return false;
}
}
public int[] getArr(){
return this.arr;
}
public void display(){
for (int i = 0; i <nElement; i++) {
System.out.println(arr[i]);
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
OrderArray h1 = new OrderArray(12);
for (int i = 0; i < 12; i++) {
h1.insert((int)(Math.random() * 1000));
}
// h1.display();
OrderArray h2 = new OrderArray(10);
for (int i = 0; i < 10; i++) {
h2.insert((int)(Math.random() * 1000));
}
h1.mearge(h1.getArr(), h2.getArr());
// System.out.println(h.find(34));
}
}
这就是对数组的二分查找法基本的学习。
- 大小: 12.7 KB
- 大小: 13.3 KB
- 大小: 111.2 KB
分享到：
相关推荐
数组是所有编程语言中最基本的数据结构之一，它允许我们存储一组相同类型的数据，并通过索引来访问它们。 在Java中，数组是一种特殊的对象，它包含固定大小的元素集合。这些元素可以是任何基本类型（如int、double...
数据结构的学习不仅包括数组，还有链表、栈、队列、树、图等多种类型。理解并熟练运用这些数据结构可以帮助我们设计更高效、更具可扩展性的算法。对于Java开发者来说，掌握数据结构是提高编程技能的关键步骤。通过...
在Java编程语言中，数组是一种基础且重要的数据结构，用于存储同类型的数据集合。在处理学生成绩统计这类问题时，数组能有效地帮助我们组织和计算数据。以下将详细讲解两个不同的Java代码方案，它们利用数组来完成...
数组是Java中最基础的数据结构之一，用于存储固定大小的同类型元素集合。数组可以在一维或多维中定义，下面分别介绍一维数组和多维数组。 ##### 1.1 一维数组 一维数组是最简单的数组形式，可以定义为： ```java ...
理解动态数组实现的线性表对于编程和数据结构的学习至关重要，它可以帮助我们更有效地管理内存，优化数据结构的性能，从而提高程序的运行效率。在实际编程中，我们可以根据需求选择适合的数据结构，如在需要快速随机...
Java数组是Java编程语言中的基本数据结构之一，用于存储固定数量的同类型元素。了解和熟练掌握数组的使用是学习Java的重要环节。本篇练习题涵盖了数组的基本概念、操作和异常处理，下面是针对题目中涉及知识点的详细...
### Java数据结构学习笔记知识点详解 #### 一、数据结构与算法基础 1. **数据结构定义** - 数据结构是一门研究组织数据方式的学科，它与编程语言紧密相关，是实现高效程序设计的基础。 - 在软件开发中，合理选择...
Java 希尔排序 算法 数据结构 数组 输出
Java 选择排序 算法 数据结构 数组 输出
在 C 语言中，字符数组是一种常用的数据结构，用于存储字符串。大小写转换是指将大写字母转换为小写字母的过程。通过使用 ASCII 码表，我们可以轻松地实现大小写转换。 例如，在程序 fun 中，我们可以使用以下代码...
在Java编程语言中，数组是存储相同类型元素集合的基本数据结构。本教程将重点讲解如何使用一维和二维数组来实现乘法表，这对于初学者来说是一个很好的实践项目，有助于理解数组的概念以及如何通过控制流程来输出特定...
资源摘要信息是关于Java数据结构和算法的知识点总结，涵盖了数组、栈与队列、链表、递归、哈希表、高级排序、二叉树、红黑树、堆、带权图等数据结构和算法概念。 一、数组 * 数组是相同类型变量的集合，可以使用...
### Java数据结构与算法学习笔记知识点总结 #### 一、数据结构概述 数据结构是对数据的一种组织形式，它决定了数据的存储方式以及处理数据的方法。常见的数据结构包括但不限于数组、链表、栈、队列、二叉树、图等...
总之，"Java版数据结构学习资料"是一个全面的学习资源，涵盖了数据结构的核心概念和常见应用。无论是初学者还是经验丰富的开发者，都能从中受益，加深对数据结构的理解，提升编程技巧。通过系统学习和实践，你将能够...
Java数组是Java编程语言中的基本数据结构之一，它允许我们存储多个同类型的元素在一个单一的变量中。数组的使用在程序设计中至关重要，因为它提供了一种高效、有序的方式来管理和访问数据。下面将深入探讨Java数组的...
在Java编程语言中，数组是一种基础且重要的数据结构，用于存储同类型的元素序列。当我们需要将两个或多个数组合并成一个大的数组时，就需要用到数组的合并技术。本篇文章将详细探讨Java中如何实现数组的合并。 首先...
Java中的数组是编程中不可或缺的基础概念，主要用于存储一组...总之，Java数组提供了一种高效、有序的方式来存储和操作一组相同类型的数据，是编程中常用的数据结构。理解和熟练使用数组是掌握Java编程的关键步骤之一。
总之，`PriorityQ.java`文件可能是一个简单的数组实现优先队列的示例，通过分析这个文件，我们可以学习到如何利用数组数据结构实现优先队列，以及理解其核心的插入、删除和查找操作。同时，这也能帮助我们更好地掌握...
在Java编程中，数组是一种非常基础且重要的数据结构，它用于存储同类型的多个元素。然而，在实际编程过程中，我们可能会遇到各种与数组操作相关的错误，其中"java.lang.ArrayIndexOutOfBoundsException"是一个常见的...