package util;
import java.util.Calendar;
/**
* 二分法查找与线性查找效率问题
* @author zhanglu
*
*/
public class DichotomyAndLinearity {
private int[] array;
public DichotomyAndLinearity(int size){
array = new int[size];
}
public void setArayValue(int index,int value){
array[index] = value;
}
public static void findlinearity(int[] array,int searchKey){
//arrayOrder(array);
int i = 0;
for( i= 0;i < array.length;i++){
if(array[i] == searchKey){
break;
}
}
if(i == array.length){
System.out.println("不存在此项:"+searchKey);
}else{
System.out.println("查找到的此项为:"+searchKey);
}
}
/**
* 二分法查找数组
* @param array
* @param searchKey
* @return
*/
public static String findDigit(int[] array,int searchKey){
//对数组先进行排序
//arrayOrder(array);
int startDigit = 0;//开始下标为0
int endDigit = array.length - 1;//结束下标
int currentDigit;
boolean flag = true;
while(flag){
currentDigit = (startDigit+endDigit)/2;
if(array[currentDigit] == searchKey){
return currentDigit+":"+searchKey;
}else if(array[currentDigit] > searchKey){
endDigit = currentDigit - 1;
}else{
startDigit = currentDigit + 1;
}
if(startDigit > endDigit){
flag = false;
return "没有找到该数据:"+searchKey;
}
}
return null;
}
public static void arrayOrder(int[] array){
for(int i = 0;i < array.length;i++){
for(int j = array.length - 1;j > 0;){
int temp;
if(array[j] < array[j-1]){
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
}
j--;
}
}
}
public static void main(String[] args) {
DichotomyAndLinearity ac = new DichotomyAndLinearity(1000000);
for(int i = 0;i < 1000000;i++){
ac.setArayValue(i, i);
}
int searchKey = 9999900;
Calendar c1 = Calendar.getInstance();
long start01 = c1.getTime().getTime();
System.out.println(findDigit(ac.array,searchKey));
Calendar c2 = Calendar.getInstance();
long start02 = c2.getTime().getTime();
System.out.println("二分法查找速度:"+(start02-start01));
Calendar c3 = Calendar.getInstance();
long start03 = c3.getTime().getTime();
findlinearity(ac.array,searchKey);
Calendar c4 = Calendar.getInstance();
long start04 = c4.getTime().getTime();
System.out.println("线性查找速度:"+(start04-start03));
}
}
二分法性在效率上要强于线性查找
分享到:
- 2009-03-13 21:11
- 浏览 828
- 评论(0)
- 论坛回复 / 浏览 (0 / 1919)
- 查看更多
相关推荐
有序二分法查找基于分治策略,适用于已排序的线性数据结构,如数组。其基本思想是将搜索区间不断缩小,直到找到目标元素或者搜索区间为空。步骤如下: 1. 计算数组中间索引。 2. 检查中间元素是否为目标值。如果是...
二分法查找,又称为折半查找,是一种在有序数组中查找特定元素的搜索算法。其核心思想是通过不断将搜索区间对半分割来缩小查找范围,从而快速定位目标值。具体步骤如下: 1. **初始化**:设置两个指针,`low`指向...
在计算机科学中,数组二分法查找是一种高效的搜索算法,尤其适用于有序数组。该方法将查找过程分成两半,每次比较中间元素与目标值,然后根据比较结果缩小搜索范围。这个过程不断递归进行,直到找到目标值或者搜索...
有序二分法查找,也称为二分搜索,是一种在有序数组中查找特定元素的搜索算法。这种方法基于分治策略,其基本思想是将数组分成两个相等(或近似相等)的部分,然后检查中间元素是否是我们要找的。如果找到,搜索结束...
二分法查找(Binary Search),又称为折半查找,是一种在有序数组中查找特定元素的高效算法。其基本思想是通过将目标值与数组中间位置的元素进行比较,不断缩小查找范围,从而提高查找效率。具体步骤如下: - 首先...
该函数实现了基于二分法查找单词的功能,接收三个参数: - `char *pDictionary`: 指向词库的指针。 - `char szKeyword[]`: 需要查找的目标单词。 - `long nDicLength`: 词库的长度(以字节为单位)。 函数返回值为...
对于一个有序数组来说,二分查找的平均时间复杂度为O(log n),相较于线性查找的O(n)具有更高的效率。 在PHP中,实现二分查找算法可以采用循环和递归两种方式。循环方式使用while循环结构,而递归方式则是通过函数...
结合提供的文件`OrderedArray`,可以推断这可能是关于有序数组的示例或练习,可能包含了如何使用数组实现二分查找或其他基于排序的算法。学习这部分内容有助于深化对数据结构和算法的理解,提高编程实践中的问题解决...
二分法,又称折半查找法,是一种在有序数组中搜索特定元素的高效算法。它主要利用了数组的线性特性,将查找范围逐步缩小,从而显著减少查找次数。在VB.NET中实现二分法查找,可以极大地提高处理海量数据时的效率,...
二分法查找则适用于有序数组,它通过不断将查找区间折半来提高效率。算法首先找到数组的中间元素,然后比较目标值与中间元素的关系,根据比较结果缩小查找范围。这种方法的优点是查找速度快,查找次数以对数增长,但...
二分法查找,又称折半查找,是一种在有序数组中高效地查找特定元素的搜索算法。这种方法的关键在于利用数组的有序性,通过不断缩小搜索范围来快速定位目标值。在这个C++版本的二分法查找中,我们将深入理解其原理,...
本主题将深入探讨“java数组与简单排序”,涵盖有序数组、线性查找和二分法查找等核心概念。 有序数组是指数组中的元素按照特定顺序排列,例如升序或降序。在处理有序数组时,我们可以利用其特性来优化查找和操作...
二分法查找的时间复杂度为O(log n),远优于线性查找的O(n)。但要注意,这种方法只适用于静态数据结构,如数组,对于动态数据结构如链表,二分查找并不适用。 在实际应用中,二分查找常用于大型数据集的预处理,如...
二分法查找算法,也称为折半查找,是一种在有序数组中查找特定元素的有效方法。在数据结构领域,它属于查找算法的一种,通常用于提高搜索效率。本篇文档"数据结构-3期(KC002) 二分法查找算法.docx"详细介绍了如何...
二分法查找,又称折半查找,是一种在有序数组中搜索特定元素的高效算法。它利用了数组的线性特性,每次将待搜索区域减半,直到找到目标元素或者确定不存在为止。这种方法大大减少了查找所需的平均时间复杂度,是...
二分查找(Binary Search),也称为折半查找,是一种在有序数组中查找某一特定元素的搜索算法。二分查找采用分而治之的策略,通过将查找区间分成前后两部分来减少查找范围,从而提高查找效率。在理想情况下,二分...
这种方法大大减少了查找次数,尤其在大型数据集上,效率远高于线性查找。 在C++中,二分查找通常用于处理已经排序的整型数组。以下是一个简单的二分查找函数的实现: ```cpp #include using namespace std; // ...
二分法查找的时间复杂度为O(log n),比线性查找效率高很多。 对于初学者,理解这些基础算法的概念、工作原理以及它们的实现方式至关重要。在实际编程中,熟练运用这些算法能有效提高代码的执行效率。在Java中,你...
二分法,也称为折半查找,是一种在有序数组中搜索特定元素的高效算法。它基于分治策略,将问题分解为更小的部分,然后逐步缩小搜索范围,直到找到目标或者确定目标不存在。在这个名为“erfenfa.rar”的压缩包中,...