Binary Search in Java
2024-10-20 15:55:07
关于折半查找中的几个注意点.
Version 1:
public static <T extends Comparable<? super T>> int binSearch(T[] arr,
T element) {
int length = arr.length;
int middle = length / 2;
int index;
if (length == 0) {
return -1;
}
if (arr[middle].compareTo(element) == 0) {
index = middle;
} else if (arr[middle].compareTo(element) < 0) {
index = middle
+ 1
+ binSearch(Arrays.copyOfRange(arr, middle + 1, length),
element);
} else {
index = binSearch(Arrays.copyOfRange(arr, 0, middle), element);
}
return index;
}
要保证接口为binSearch(array, target)，所以此处使用了Arrays.copyOfRange()--导致造成了额外的空间消耗（创建新的数组）。
Version 2:
// 注意这种切换接口的方式
public static <T extends Comparable<? super T>> int binSearch_JDK(T[] arr,
T element) {
//With Recursion
return binSearch_JDK(arr, 0, arr.length - 1, element);
} // With Recursion
public static <T extends Comparable<? super T>> int binSearch_JDK(T[] arr, int start, int end, T element) {
if(start > end){
return -1;
}
int middle = (start + end) / 2;
if(arr[middle].compareTo(element) == 0){
return middle;
}else if(arr[middle].compareTo(element) < 0){
return binSearch_JDK(arr, middle + 1, end, element);
}else{
return binSearch_JDK(arr, 0, middle - 1, element);
}
}
保证了接口原型不变，而且没有额外的空间消耗（创建新的数组）。注意这种切换接口的方式。
Version 3:
// 注意这种切换接口的方式
public static <T extends Comparable<? super T>> int binSearch_JDK(T[] arr,
T element) {
//Without Recursion
return binarySearch(arr, 0, arr.length - 1, element);
} // JDK SOURCE CODE jdk没有使用泛型，而是直接使用了long
// 能不用递归就不要用
public static <T extends Comparable<? super T>> int binarySearch(T[] arr, int start, int end, T element) {
int middle = start;
while(start <= end){
//middle = (start + end) / 2;
middle = (start + end) >>> 1;
if(arr[middle].compareTo(element) == 0){
return middle;
}else if(arr[middle].compareTo(element) < 0){
start = middle + 1;
}else{
end = middle - 1;
}
}
return -1;
}
这种方法相对于前2种方法要好很多：接口原型不变，而且没有额外的空间消耗（创建新的数组）并且没有使用递归。
最新文章
- GDB调试32位汇编堆栈分析
- Jenkins Job 自杀 groovy
- Mac OS X 系统12个常用的文本编辑快捷键（移动、选中）
- Python入门版
- DOCTYPE html PUBLIC 指定了 HTML 文档遵循的文档类型定义
- [Linux&Vim]基础01
- zend studio使用入门
- Linux screen 常用命令
- Hashtable、ConcurrentHashMap源码分析
- VS2008 C++ 利用WinHttp API获取Http请求/响应头部Header
- Mybatis按顺序获取数据
- shell 脚本中执行SQL语句 -e "..."
- 相对路径和绝对路径的问题"/"带不带斜杠
- 我眼中的 Nginx（五）：Nginx — 子请求设计之道
- Win10外包公司（长年承接Win10App外包、Win10通用应用外包）
- druid:java代码创建连接池
- MySQL字符集不一致的解决办法总结
- Python之路(第七篇)Python作用域、匿名函数、函数式编程、map函数、filter函数、reduce函数
- QT中的一些信号
- Python -- 网络编程 -- 简单抓取网页