当前位置:首页 > 开发 > 编程语言 > Java > 正文

java 二分查找

发表于: 2014-12-20   作者:shuizhaosi888   来源:转载   浏览:
摘要: 需求:在排好顺序的一串数字中,找到数字T   一般解法:从左到右扫描数据,其运行花费线性时间O(N)。然而这个算法并没有用到该表已经排序的事实。 /** * * @param array * 顺序数组 * @param t * 要查找对象 * @return */ public stati

需求:在排好顺序的一串数字中,找到数字T

 

一般解法:从左到右扫描数据,其运行花费线性时间O(N)。然而这个算法并没有用到该表已经排序的事实。

	/**
	 * 
	 * @param array
	 *            顺序数组
	 * @param t
	 *            要查找对象
	 * @return
	 */
	public static <T extends Comparable<? super T>> int Search(T[] array, T t) {
		for (int i = 0; i < array.length; i++) {// 顺序比较
			if (t.compareTo(array[i]) == 0) {
				return i;
			}
		}
		return -1;
	}

 

 

好的解法:验证T是否是居中的元素,如果是就找到了,如果小于(说明居中右侧数据都>T),那么可以用同样的策略于居中元素左侧已经排序的子序列,如果大于,同理。

	/**
	 * 
	 * @param array
	 *            顺序数组
	 * @param t
	 *            要查找对象
	 * @return
	 */
	public static <T extends Comparable<? super T>> int binarySearch(T[] array, T t) {
		int low = 0;// 下限
		int high = array.length - 1; // 上限
		while (low <= high) {
			int i = (low + high) / 2;
			if (t.compareTo(array[i]) > 0) {
				low = i + 1; // 重置下限
			} else if (t.compareTo(array[i]) < 0) {
				high = i - 1;// 重置上限
			} else {
				return i;
			}
		}
		return -1;
	}

       

 

 

        折半查找提供了在O(logN)时间内的contains操作,但是所有其他操作均需要O(N)时间。

        在数据是稳定(即不允许插入操作和删除操作)的应用中,这种操作可能是非常有用的。此时输入数据只需要一次排序,但是此后访问会很快。

 

        大多数时候算法表达式的简明性是以速度的降低为代价的。

 

 

 

 

 

java 二分查找

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号