我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:爱彩网 > 二分搜索 >

JAVA 二分算法只能对数字进行查找吗

归档日期:06-27       文本归类:二分搜索      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部不要死脑筋。作为一个程序员最怕这个了。如果一个集合满足下列条件都可以:

  1.对于任何两个元素x,y,都有x=y或者y=x;(=不是小于等于,看下离散数学)

  2分法查找,前提是要有序,要排序,必然要比较大小,所以只要一个类它实现了Comparable接口的compareTo(To)方法(Comparable在g包中)或是实现一个比较器对象接口Comparator(Comparator在java.util包),都可以进行比较了。不管是String型,计本数据类型,还是其他什么的,都可以用2分发查找了。给你看看API

  Tkey)使用二分搜索法搜索指定列表,以获得指定对象。在进行此调用之前,必须根据列表元素的自然顺序对列表进行升序排序(通过sort(List)方法)。如果没有对列表进行排序,则结果是不确定的。如果列表包含多个等于指定对象的元素,则无法保证找到的是哪一个。

  此方法对“随机访问”列表运行log(n)次(它提供接近固定时间的位置访问)。如果指定列表没有实现RandomAccess接口并且是一个大型列表,则此方法将执行基于迭代器的二分搜索,执行O(n)次链接遍历和O(logn)次元素比较。

  如果搜索键包含在列表中,则返回搜索键的索引;否则返回(-(插入点)-1)。插入点被定义为将键插入列表的那一点:即第一个大于此键的元素索引;如果列表中的所有元素都小于指定的键,则为list.size()。注意,这保证了当且仅当此键被找到时,返回的值将=0。

  ClassCastException-如果列表中包含不可相互比较的元素(例如,字符串和整数),或者搜索键无法与列表的元素进行相互比较。

  Comparator?superTc)使用二分搜索法搜索指定列表,以获得指定对象。在进行此调用之前,必须根据指定的比较器对列表进行升序排序(通过sort(List,Comparator)方法)。如果没有对列表进行排序,则结果是不确定的。如果列表包含多个等于指定对象的元素,则无法保证找到的是哪一个。

  此方法对“随机访问”的列表运行log(n)次(它提供接近固定时间的位置访问)。如果指定列表没有实现RandomAccess接口并且是一个大型列表,则此方法将执行基于迭代器的二分搜索,执行O(n)次链接遍历和O(logn)次元素比较。

  如果搜索键包含在列表中,则返回搜索键的索引;否则返回(-(插入点)-1)。插入点被定义为将键插入列表的那一点:即第一个大于此键的元素索引;如果列表中的所有元素都小于指定的键,则为list.size()。注意,这保证了当且仅当此键被找到时,返回的值将=0。

  ClassCastException-如果列表中包含使用指定的比较器不可相互比较的元素,或者使用此比较器无法相互比较搜索键与列表元素。

  Aintcompare(To1,To2)比较用来排序的两个参数。根据第一个参数小于、等于或大于第二个参数分别返回负整数、零或正整数。

  在前面的描述中,符号sgn(expression)表示signum数学函数,根据expression的值为负数、0还是正数,该函数分别返回-1、0或1。

  虽然这种情况很普遍,但并不严格要求(compare(x,y)==0)==(x.equals(y))。一般说来,任何违背这个条件的Comparator都应该清楚地指出这一事实。推荐的语言是“注意:此Comparator强行进行与equals不一致的排序。”

  注意,不重写Object.equals(Object)方法总是安全的。然而,在某些情况下,重写此方法可以允许程序确定两个不同的Comparator是否强行实施了相同的排序,从而提高性能。

  仅当指定的对象也是一个Comparator,并且强行实施与此Comparator相同的排序时才返回true。

  publicinterfaceComparableT此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序,类的compareTo方法被称为它的自然比较方法。

  实现此接口的对象列表(和数组)可以通过Collections.sort(和Arrays.sort)进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的元素,无需指定比较器。

  建议(虽然不是必需的)最好使自然排序与equals一致。这是因为在使用自然排序与equals不一致的元素(或键)时,没有显式比较器的有序集合(和有序映射表)行为表现“怪异”。尤其是,这样的有序集合(或有序映射表)违背了根据equals方法定义的集合(或映射表)的常规协定。

  例如,如果将两个键a和b添加到没有使用显式比较器的有序集合中,使(!a.equals(b)&&a.compareTo(b)==0),那么第二个add操作将返回false(有序集合的大小没有增加),因为从有序集合的角度来看,a和b是相等的。

  实际上,所有实现Comparable的Java核心类都具有与equals一致的自然排序。java.math.BigDecimal是个例外,它的自然排序将值相等但精确度不同的BigDecimal对象(比如4.0和4.00)视为相等。

  它直接遵循compareTo的协定,商是C的等价关系,自然排序是C的整体排序。当说到类的自然排序与equals一致时,是指自然排序的商是由类的equals(Object)方法定义的等价关系。

  intcompareTo(To)比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象,则分别返回负整数、零或正整数。

  在前面的描述中,符号sgn(expression)指定signum数学函数,该函数根据expression的值是负数、零还是正数,分别返回-1、0或1中的一个值。

  ClassCastException-如果指定对象的类型不允许它与此对象进行比较。

本文链接:http://pikeducation.com/erfensousuo/415.html