当前位置:首页 > 开发 > 编程语言 > 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

    震惊

    震惊

编辑推荐
查询二叉树是平衡树->红黑树的基础,红黑树是TreeMap和TreeSet实现的基础。 深度:根到任意节点
编程之美在于算法之美,先来看看二分查找的算法: 隐藏条件:二分查找必须是有序的,从小到大,或从
环境:Notpad ++ 6.0 + JDK 6.0.24 问题:用Java实现二分查找算法 算法剖析: 二分查找是在一个有序
#include <iostream> using namespace std; /** * 二分查找之一: 可以找到连续重复出现的第
第一步 #include<iostream> using namespace std; int binarySearch(int a[], int x, int n)
二分查找 #include <stdio.h> #define N 10 int f(int a[],int low,int high,int x) { int mi
二分查找又称折半查找,它是一种效率较高的查找方法。   【二分查找要求】:1.必须采用顺序存储结
直接插入排序 直接插入排序的原理:先将原序列分为有序区和无序区,然后再经过比较和后移操作将无序
算法-查找之二二分查找 顺序查找【算法-查找之一】顺序查找是最简单的查找策略,易于分析,适用于小
二分查找细则讨论 二分查找有两种实现方式:非递归和递归。我们首先给出非递归的实现,然后对其中的
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号