Java面试题Java写一个折半查找
引导语:折半查找是指如果不是从一组随机的序列里查找,而是从一组排好序的序列里找出某个元素的位置,则可以有更快的算法。以下是本站小编分享给大家的用Java面试题Java写一个折半查找,欢迎阅读参考!
用Java写一个折半查找
答:折半查找,也称二分查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的.那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组已经为空,则表示找不到指定的元素。这种搜索算法每一次比较都使搜索范围缩小一半,其时间复杂度是O(logN)。
123456789101112131415161718192021222324252627282930313233343536373839404142434445 | import arator; public class MyUtil {
public static <T extends Comparable<T>> int binarySearch(T[] x, T key) {
return binarySearch(x, 0 , th- 1 , key);
}
// 使用循环实现的二分查找
public static <T> int binarySearch(T[] x, T key, Comparator<T> comp) {
int low = 0 ;
int high = th - 1 ;
while (low <= high) {
int mid = (low + high) >>> 1 ;
int cmp = are(x[mid], key);
if (cmp < 0 ) {
low= mid + 1 ;
}
else if (cmp > 0 ) {
high= mid - 1 ;
}
else {
return mid;
}
}
return - 1 ;
}
// 使用递归实现的二分查找
private static <T extends Comparable<T>> int binarySearch(T[] x, int low, int high, T key) {
if (low <= high) {
int mid = low + ((high -low) >> 1 );
if (areTo(x[mid])== 0 ) {
return mid;
}
else if (areTo(x[mid])< 0 ) {
return binarySearch(x,low, mid - 1 , key);
}
else {
return binarySearch(x,mid + 1 , high, key);
}
}
return - 1 ;
} } |
说明:上面的代码中给出了折半查找的两个版本,一个用递归实现,一个用循环实现。需要注意的是计算中间位置时不应该使用(high+ low) / 2的方式,因为加法运算可能导致整数越界,这里应该使用以下三种方式之一:low + (high – low) / 2或low + (high – low) >> 1或(low + high) >>> 1(>>>是逻辑右移,是不带符号位的右移)
-
Java Class文件是什么
Class类是在Java语言中定义一个特定类的实现。一个类的定义包含成员变量,成员方法,还有这个类实现的接口,以及这个类的父类。Class类的对象用于表示当前运行的Java应用程序中的类和接口。比如:每个数组均属于一个Class类对象,所有具有相同元素类型和维数的数组共享...
-
Java测试题及答案
Java测试题及答案学习是把知识能力思维方法等转化为你的私有产权的重要手段,是公有转私的重要途径。以下是本站小编整理的Java测试题及答案,欢迎学习!试题1指出下面语句没有编译错误的是()。A.longn=999999999999;n=999999999999L;C.longn=999999999999L;D.doubl...
-
计算机二级JAVA考试强化训练题(单选)
为帮助考生们更快第掌握二级JAVA相应知识点,以下是本站小编搜索整理的一份计算机二级JAVA考试强化训练题(单选),供参考练习,预祝考生们考出自己理想的成绩!想了解更多相关信息请持续关注我们应届毕业生考试网!单选题1).下列关于Applet的安全限制的叙述中,错误的是(...
-
新手学习Java最高效的10个计划
对于新手来说学习Java如同堵天书,下面是本站小编收集的关于新手学习Java最高效的10个计划,希望可以为您的学习带来帮助!计划一:了解未来技术发展方向两耳不闻窗外事,在如今是不合适的,尤其是在瞬息万变的互联网时代,作为一个开发者技术跟不上可以去专研,思想要跟不上,...