在JDK1.5或之前版本的JDK中,类java.util.Arrays中有二分查找法binarySearch(type[],int key),如:
public static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length-1;
while (low <= high) {
int mid = (low + high) >> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
有一个隐患:
int mid = (low + high) >> 1;
一般情况下是不会有问题的(因为不会有这么长的Array),但可能在64位的机器上,当low + high超出整数的最大值的时候会出现难以预料的错误结果或死循环,但不报错。
以上代码的作者是Joshua Bloch,他是《Effective Java》的作者, 也是Sun的杰出工程师。Josh Bloch 早就在博客中发表文章就为JDK中存在了这么久的Bug感到焦虑。
还好在JDK1.6中有了改进,但我觉得不是最好的解决方案。
在JDK1.6中改成了如下:
int mid = (low + high) >>> 1;
这样的话,当low + high超出整数的最大值的时候会抛出ArrayIndexOutOfBoundsException异常,因为mid是负数。
但我觉得这样并不是最好的解决办法,我很奇怪为什么不修改成下面的,就可以输出正确结果
int mid = (low >> 2) + ( high >> 2);
分享到:
相关推荐
### Java.util.logging.Logger 使用详解 #### 一、创建Logger对象 在Java中,`java.util.logging.Logger` 是标准的日志框架之一,它提供了基础的日志记录功能。为了使用这一功能,首先需要获得 `java.util.logging...
### Java.util.Date与Java.sql.Date互转及字符串转换为日期时间格式 #### 一、Java.util.Date与Java.sql.Date的基本概念 在Java编程语言中,处理日期和时间时经常使用到`java.util.Date`和`java.sql.Date`这两个类...
### Java.util.Date与Java.sql.Date相互转换 #### 知识点概述 在Java开发中,经常需要处理日期和时间相关的操作。Java标准库提供了两个重要的日期类:`java.util.Date` 和 `java.sql.Date`。虽然它们名字相似,但...
### 使用 Java.util.zip 包实现数据压缩与解压 在计算机科学领域,数据压缩技术是一项重要的功能,它能够帮助减少存储空间的需求以及提高网络传输效率。本文将通过一系列的示例来详细介绍如何利用 Java 中的 `java....
1. java.util.concurrent - Java 并发工具包 2. 阻塞队列 BlockingQueue 3. 数组阻塞队列 ArrayBlockingQueue 4. 延迟队列 DelayQueue 5. 链阻塞队列 LinkedBlockingQueue 6. 具有优先级的阻塞队列 ...
在Java编程语言中,`java.util.InputMismatchException`是一个常见的运行时异常,它通常发生在尝试从数据源(如控制台、文件或数据库)读取数据时,遇到的数据类型与预期的不匹配。在这个特定的场景中,问题出在主线...
"java.util.concurrent.ExecutionException: java.lang.OutOfMemoryError" 是一个典型的错误提示,它表明在并发执行过程中遇到了内存不足的问题。下面我们将深入探讨这个问题的原因、影响以及如何解决。 内存溢出...
Java.util.ConcurrentModificationException 异常问题详解 ConcurrentModificationException 异常是 Java 中一个常见的异常,它发生在 Iterator 遍历集合时,集合同时被修改引起的异常。在 Java 中,集合类如 ...
Java提供日期(Data)类、日历(Calendar)类,随机数(Random)类,堆栈(Stack)、向量(Vector) 、位集合(Bitset)以及哈希表(Hashtable)等类来表示相应的数据结构
Java编程语言提供了两个重要的日期处理类,分别是`java.util.Date`和`java.sql.Date`,它们在处理日期和时间上有着不同的特性和用途。 `java.util.Date`是更通用的日期时间类,它包含了日期和时间的信息,可以精确...
Java.sql.Date与Java.util.Date的区别和转换 Java.util.Date和Java.sql.Date是Java中两种不同的日期和时间表示方式,虽然它们都是表示日期和时间,但是它们之间存在着一些重要的区别。 首先,Java.util.Date是Java...
这是我在编写struts2中遇到的问题,整理出来,包括截图,希望可以帮到大家
Java.util.Date与java.sql.Date的互转及字符串转换为日期时间格式 java.util.Date和java.sql.Date是Java中两个常用的日期时间类,分别属于不同的包。java.util.Date是Java标准库中的日期时间类,而java.sql.Date是...
一个高性能的Java线程库,该库是 JDK 1.5 中的 java.util.concurrent 包的补充,可用于基于并发消息机制的应用。该类库不提供远程的消息功能,其设计的宗旨是实现一个内存中的消息传递机制. 主要特点有: * All ...
Java.util包是Java标准库中的核心包之一,它包含了大量用于日常编程的工具类和接口。这个包在Java 2版本中得到了显著增强,引入了许多重要的数据结构和算法,为Java程序员提供了更丰富的功能。 首先,Java.util包中...