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

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

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

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++) {

arrhttp://ay[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]) JvToMDNkB{

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();来获取当前时间，来计算该算法运行运算时间http:// ​​​​​​​ 顺序查找的时间复杂度为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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。