- 相关推荐
Java面试题Java写一个折半查找
引导语：折半查找是指如果不是从一组随机的序列里查找,而是从一组排好序的序列里找出某个元素的位置,则可以有更快的算法。以下是百分网小编分享给大家的用Java面试题Java写一个折半查找，欢迎阅读参考!
用Java写一个折半查找
答：折半查找，也称二分查找、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束;如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组已经为空，则表示找不到指定的元素。这种搜索算法每一次比较都使搜索范围缩小一半，其时间复杂度是O(logN)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
import java.util.Comparator;public class MyUtil { public static <T extends Comparable<T>> int binarySearch(T[] x, T key) { return binarySearch(x, 0, x.length- 1, key); } // 使用循环实现的二分查找 public static <T> int binarySearch(T[] x, T key, Comparator<T> comp) { int low = 0; int high = x.length - 1; while (low <= high) { int mid = (low + high) >>> 1; int cmp = comp.compare(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(key.compareTo(x[mid])== 0) { return mid; } else if(key.compareTo(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面试题Java写一个折半查找】相关文章：
Java面试题（精选）06-30
java面试题05-20
Java线程面试题08-25
高级Java面试题精选11-02
Java 问答面试题09-03
Java原理面试题07-13
经典Java基础面试题08-13
C语言二分查找（折半查找）算法及代码08-07