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

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;
 }
} 

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;
			}
		}
	}
 
}