浅谈二分法查找和原始算法查找的效率对比

我就废话不多说了,大家还是直接看代码吧!

import java.text.MessageFormat;
public class AppTest {
 static int length = 70000000;
 static int[] array = new int[length];

 static {
  for (int i = 0; i < length; i++) {
   array[i] = i;
  }
 }

 public static void main(String[] args) {
  for (int i = 0; i < 10; i++) {
   int target = (int) (Math.random() * length * 2);
   long start_f1 = System.currentTimeMillis();
   int index_f1 = findIndex(array, target);
   long end_f1 = System.currentTimeMillis();
   long time_f1 = end_f1 - start_f1;

   long start_f2 = System.currentTimeMillis();
   int index_f2 = findIndexByFor(array, target);
   long end_f2 = System.currentTimeMillis();
   long time_f2 = end_f2 - start_f2;
   System.out.println(MessageFormat.format("目标数据:{0}\t二分法耗时:{1}\t普通方法耗时:{2}\t二分法结果:{3}\t普通方法结果:{4}",
               target, time_f1, time_f2, index_f1, index_f2));
  }
 }

 public static int findIndex(int[] arr, int target) {
  return findIndex(arr, 0, arr.length, target);
 }

 public static int findIndex(int[] arr, int start, int end, int target) {
  int middle = (start + end) / 2;
  if (target == arr[middle]) {
   return middle;
  } else if (start > end ||
    target < arr[0] ||
    target > arr[arr.length - 1]) {
   return -1;
  } else if (target < arr[middle]) {
   return findIndex(arr, start, middle - 1, target);
  } else if (target > arr[middle]) {
   return findIndex(arr, middle + 1, end, target);
  }
  return -1;
 }

 public static int findIndexByFor(int[] arr, int target) {
  int index = 0;
  for (int i : arr) {
   if (i == target) {
    return index;
   }
   index++;
  }
  return -1;
 }
} 

查找结果:

总结:

总结过我们可以看出,二分法查找几乎是不耗时,所以方法是很重要的

补充知识:顺序查找与二分查找时间复杂度的比较

注意要点:通过System.currentTimeMills();来获取当前时间,来计算该算法运行运算时间 ​​​​​​​ 顺序查找的时间复杂度为O(n)

二分查找的时间复杂度为O(log(n))

但两者的运行时间的结果却千差万别,可知当计算量很大的情况下算法优化的必要性。

import java.util.Arrays;

public class Main {
	public static int a[] = new int[10000*10000];

	public static void main(String[] args) {
		for(int i = 0; i < 10000* 10000; i ++) {
			a[i] = i + 1;
		}
		int target = 10000 * 10000;
//计算顺序查找所用时间
		long start = System.currentTimeMillis();
		find(target);
		long end = System.currentTimeMillis();
		System.out.println(end - start + "ms");
//计算二分查找所用时间
	 start = System.currentTimeMillis();
		Arrays.binarySearch(a, target);
		end = System.currentTimeMillis();
		System.out.println(end - start + "ms");

	}

	private static void find(int target) {
		for(int i = 0; i < 10000 * 10000; i ++) {
			if(a[i] == target) {
				return;
			}
		}
	}

}

运行结果:

55ms

0ms

以上这篇浅谈二分法查找和原始算法查找的效率对比就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • Java8 Stream对两个 List 遍历匹配数据的优化处理操作

    使用场景,有两个List<Map<String,Object>>集合,第一个集合的所有元素都是需要保留的. 第一个集合的值为: {name=张三丰1, id=1} {name=张三丰2, id=2} {name=张三丰3, id=3} {name=张三丰4, id=4} {name=张三丰5, id=5} {name=张三丰6, id=6} {name=张三丰7, id=7} {name=张三丰8, id=8} 第二个集合的值为: {grade=61, id=1} {grade=6

  • Java Integer.valueOf()和Integer.parseInt()的区别说明

    前言 大家都知道Integer类中有Integer.valueOf(String s)和Integer.parseInt(String s)两个静态方法,他们都能够将字符串转换为整型.说到这里你肯定会想同一个功能为什么要提供两个不同的方法,这不是浪费吗? 区别 Integer.parseInt(String s)将会返回int常量. Integer.valueOf(String s)将会返回Integer类型,如果存在缓存将会返回缓存中已有的对象. 使用不当将会产生的问题 由于Java的自动拆箱

  • java8新特性 stream流的方式遍历集合和数组操作

    前言: 在没有接触java8的时候,我们遍历一个集合都是用循环的方式,从第一条数据遍历到最后一条数据,现在思考一个问题,为什么要使用循环,因为要进行遍历,但是遍历不是唯一的方式,遍历是指每一个元素逐一进行处理(目的),而并不是从第一个到最后一个顺次处理的循环,前者是目的,后者是方式. 所以为了让遍历的方式更加优雅,出现了流(stream)! 1.流的目的在于强掉做什么 假设一个案例:将集合A根据条件1过滤为子集B,然后根据条件2过滤为子集C 在没有引入流之前我们的做法可能为: public cl

  • java8从list集合中取出某一属性的值的集合案例

    我就废话不多说了,大家还是直接看代码吧~ List<Order> list = new ArrayList<User>(); Order o1 = new Order("1","MCS-2019-1123"); list.add(o1 ); Order o2= new Order("2","MCS-2019-1124"); list.add(o2); Order o3= new Order("

  • 浅谈二分法查找和原始算法查找的效率对比

    我就废话不多说了,大家还是直接看代码吧! import java.text.MessageFormat; public class AppTest { static int length = 70000000; static int[] array = new int[length]; static { for (int i = 0; i < length; i++) { array[i] = i; } } public static void main(String[] args) { for

  • 浅谈C++继承中的名字查找

    实例如下: #include<iostream> #include<string> using namespace std; class Base { public: void func() { cout << "func() in Base." << endl; } void func(int a) { cout << "func(int a) in Base." << endl; } voi

  • 浅谈选择、冒泡排序,二分查找法以及一些for循环的灵活运用

    如下所示: import java.util.Arrays; //冒泡排序 public class Test { public static void main(String[] args) { int[] array = { 31, 22, 15, 77, 52, 32, 18, 25, 16, 7 }; // 冒泡 --> 两两比较 --> 提取出最大的数 在最后一位 //拿第一位和它后面的一位进行 两两比较 System.out.println(Arrays.toString(arra

  • 浅谈PyQt5 的帮助文档查找方法,可以查看每个类的方法

    事情是这样的,我在python中安装了PyQt5后,想查看QtGui模块中的类QMainWindow有哪些方法, 如何查看呢? 解决方法: 1.原来在安装PyQt5时相应的帮助文档已经在安装目录里面了. 2.打开 python安装目录\C:\Users\Administrator\AppData\Local\Programs\Python\Python35-32\Lib\site-packages\PyQt5\doc\html 3.打开class_reference.html 以上这篇浅谈PyQ

  • 浅谈Java常见的排序算法

    目录 一.直接插入排序 二. 希尔排序 三.冒泡排序 四.快速排序 五.选择排序(Selection Sort) 六.堆排序 七.归并排序 一.直接插入排序 基本思想: 将一个记录插入到已排序的有序表中,使插入后的表仍然有序 对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序 package Sort; //插入排序 public class InsertSort { public static void main(String[] args) { int [] ar

  • 浅谈SpringBoot项目如何让前端开发提高效率(小技巧)

    社会分工越来越细,对于工程类研发来说,全栈是越来越少了.这是时代的进步,也是个体的悲哀. 今天要分享的小技巧,或许能够大幅提高你的开发效率.你可以用省下来的时间打个盹,浏览个美女写真什么的. 本篇文章涉及的知识点有 Swagger 为了文档 Nginx 为了效率 众所周知, java 项目的启动速度就像沙子里走路.要是你的前端模块也很大,有一大堆 node_modules , SpringBoot 会毫不犹豫的给你打包进去.每次修改前端页面,都需要打包才能调试,真是等的媳妇都跑了.可惜的是, v

  • 浅谈Java实现回溯算法之八皇后问题

    目录 一.前言 二.浅谈递归 三.回溯算法 四.八皇后问题 五.八皇后变种 六.总结 一.前言 说起八皇后问题,它是一道回溯算法类的经典问题,也可能是我们大部分人在上数据结构或者算法课上遇到过的最难的一道题-- 二.浅谈递归 对于递归算法,我觉得掌握递归是入门数据结构与算法的关键,因为后面学习很多操作涉及到递归,例如链表的一些操作.树的遍历和一些操作.图的dfs.快排.归并排序等等. 递归的实质还是借助栈实现一些操作,利用递归能够完成的操作使用栈都能够完成,并且利用栈的话可以很好的控制停止,效率

  • 浅谈算法之最小生成树Kruskal的Python实现

    目录 一.前言 二.树是什么 三.从图到树 四.解决生成问题 五.从生成树到最小生成树 六.实际问题与代码实现 七.结尾 一.前言 我们先不讲算法的原理,也不讲一些七七八八的概念,因为对于初学者来说,看到这些术语和概念往往会很头疼.头疼也是正常的,因为无端突然出现这么多信息,都不知道它们是怎么来的,也不知道这些信息有什么用,自然就会觉得头疼.这也是很多人学习算法热情很高,但是最后又被劝退的原因. 我们先不讲什么叫生成树,怎么生成树,有向图.无向图这些,先简单点,从最基本的内容开始,完整地将这个算

  • 浅谈c语言中一种典型的排列组合算法

    c语言中的全排列算法和组合数算法在实际问题中应用非常之广,但算法有许许多多,而我个人认为方法不必记太多,最好只记熟一种即可,一招鲜亦可吃遍天 全排列: #include<stdio.h> void swap(int *p1,int *p2) { int t=*p1; *p1=*p2; *p2=t; } void permutation(int a[],int index,int size) { if(index==size) { for(int i=0;i<size;i++) print

  • 详解常用查找数据结构及算法(Python实现)

    一.基本概念 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录). 查找表(Search Table):由同一类型的数据元素(或记录)构成的集合 关键字(Key):数据元素中某个数据项的值,又称为键值. 主键(Primary Key):可唯一地标识某个数据元素或记录的关键字. 查找表按照操作方式可分为: 静态查找表(Static Search Table):只做查找操作的查找表.它的主要操作是: 查询某个"特定的"数据元素是否在表中

随机推荐