我就废话不多说了,大家还是直接看代码吧!
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
以上这篇浅谈二分法查找和原始算法查找的效率对比就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持小牛知识库。
主要内容:二分查找算法的实现思路,二分查找算法的具体实现二分查找又称 折半查找、 二分搜索、 折半搜索等,是在 分治算法基础上设计出来的查找算法,对应的时间复杂度为 。 二分查找算法仅适用于有序序列,它只能用在升序序列或者降序序列中查找目标元素。 二分查找算法的实现思路 在有序序列中,使用二分查找算法搜索目标元素的核心思想是:不断地缩小搜索区域,降低查找目标元素的难度。 以在升序序列中查找目标元素为例,二分查找算法的实现思路是: 初始状态下,将整个序列
主要内容:折半查找算法,折半查找的性能分析,总结折半查找,也称 二分查找,在某些情况下相比于顺序查找,使用折半查找算法的效率更高。 但是该算法的使用的前提是静态查找表中的数据必须是有序的。 例如,在 这个查找表使用折半查找算法查找数据之前,需要首先对该表中的数据按照所查的关键字进行排序: 。 在折半查找之前对查找表按照所查的关键字进行排序的意思是:若查找表中存储的数据元素含有多个关键字时,使用哪种关键字做折半查找,就需要提前以该关键字对所有数据
本文向大家介绍JavaScript折半查找(二分查找)算法原理与实现方法示例,包括了JavaScript折半查找(二分查找)算法原理与实现方法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了JavaScript折半查找(二分查找)算法原理与实现方法。分享给大家供大家参考,具体如下: 一、问题描述: 在一个升序数组中,使用折半查找得到要查询的值的索引位置。如: 注:折半查找必须在有序数组
本文向大家介绍Java 二分查找算法的实现,包括了Java 二分查找算法的实现的使用技巧和注意事项,需要的朋友参考一下 二分查找又称折半查找,它是一种效率较高的查找方法。 折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小 于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一
本文向大家介绍C#二分查找算法实例分析,包括了C#二分查找算法实例分析的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了C#二分查找算法。分享给大家供大家参考。具体实现方法如下: 希望本文所述对大家的C#程序设计有所帮助。
标准二分的框架 while(st < ed) { int mid= st + (ed-st)/2; if( r[mid] < target) st = mid+1; else ed = mid; } return st; 二分有几个关键点需要注意: 二分的关键就是st和ed两个指针如何移动。需要记住的是,st只会往大的方向移动,ed只会往小