Java二分查询与普通查询性能对比

   public static void main(String[] args) {
		int[] nums = new int[10000000];
		for (int i = 0; i < 10000000; i++) {
			nums[i] = i;
		}
		commonSearch(nums, 10000000 - 1); //普通查询
		binarySearch(nums, 10000000 - 1); //二分查询

	}

// 普通查询
	public static void commonSearch(int nums[], int snum) {
		long timsf = System.nanoTime();
		for (int i = 0, len = nums.length; i < len; i++) {
			if (nums[i] == snum) {
				System.out.println("普通循环总共循环：" + (i + 1) + "次");
				break;
			}
		}
		long timse = System.nanoTime();
		System.out.println("普通循环总共耗时：" + (timse - timsf) + "ns");
	}

// 二分查询
	public static void binarySearch(int nums[], int snum) {
		int index = 0;
		int low = 0;
		int hig = nums.length - 1;
		long timsf = System.nanoTime();
		for (int i = 0, len = nums.length; i < len; i++) {
			index = (low + hig) / 2;
			if (nums[index] == snum) {
				System.out.println("二分查询总共循环：" + (i + 1) + "次");
				break;
			} else if (nums[index] < snum) {
				low = index + 1;
			} else {
				hig = index - 1;
			}
		}
		long timse = System.nanoTime();
		System.out.println("二分查询总共耗时：" + (timse - timsf) + "ns");
	}

执行结果：
普通循环总共循环：10000000次
普通循环总共耗时：22860745ns
二分查询总共循环：24次
二分查询总共耗时：65987ns

long timse = System.nanoTime();

"这里为了体现性能结果采用纳秒来计算。"

评论

3 楼 trnnn 2012-07-31  

个人拙见：这个 System.out.println 这样的输出语句 还是不要写在性能测试的主题代码里头比较好，因为这个out相当耗时间。第二，因为JVM对执行性能的优化 同一个方法第一次执行 和第二次执行的时间有很大差别，最好把同一个代码段预先执行三到五次，才能达到最佳性能

2 楼 wuxing429 2012-07-30  

二分查找  排序好的时间当然少   你这个其实是循环了m/n 而普通查找是n

1 楼 love_ysys 2012-07-30  

要是查询的数字就是第一个或者比较靠前呢？。。。所谓的这些查找方法各有优缺点，不限定哪个一定就更好。。。