一、查找算法
常见的查找算法大概有顺序查找、二分查找、二叉排序树查找、哈希表法（散列表）、分块查找等，
下面简单了解一下其他几种查找算法。
1.顺序查找
也就是暴力方法，按顺序比较每个元素，直到找到关键字为止。
条件：无序或有序数据，时间复杂度：O(n)
2.二叉排序树查找
二叉排序树的性质：
1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉排序树。
在二叉查找树b中查找x的过程为：
1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则：
3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
4. 查找右子树。
时间复杂度：O(\log_2(n))
3.哈希表查找
创建哈希表（散列表）
哈希查找的操作步骤：⑴用给定的哈希函数构造哈希表⑵根据选择的冲突处理方法解决地址冲突⑶在哈希表的基础上执行哈希查找。
建立哈希表操作步骤： ① 取数据元素的关键字key，计算其哈希 函数值。若该地址对应的存储 空间还没有被占用，则将该元素存入；否则执行step2解决冲突。 ② 根据选择的冲突处理方法，计算关键字 key的下一个存储地址。若下一个存储地 址仍被占用，则继续执行step2，直到找 到能用的存储地址为止。
时间复杂度：几乎是O(1)，取决于产生冲突的多少。
4.分块查找
将n个数据元素"按块有序"划分为m块（m ≤ n）。
每一块中的结点不必有序，但块与块之间必须"按块有序"；
即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；
而第2块中任一元素又都必须小于第3块中的任一元素，……。
然后使用二分查找及顺序查找。
二、二分查找
一般是操作有序数组，查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。时间复杂度：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
46
47
48
49
50
51
52
|
public
static
int
binSearch(
int
[] arr,
int
des){
if
(arr==
null
|| arr.length<
1
){
return
-
1
;
}
int
left=
0
;
int
right=arr.length-
1
;
//注意防止数组下标越界
/**
* 这里的判断条件必须包含等于，
* 考虑{1,2,3}，查找1，如果不判断等于，就丢失了比较导致查找错误
*/
while
(left<=right){
int
mid=left+(right-left)/
2
;
if
(des==arr[mid]){
return
mid;
}
else
if
(des<arr[mid]){
//舍弃右侧
/**
* 注意，此处的mid已经参与过比较了并失败了，
* 所以重新二分不要包含进来，下同
*/
right=mid-
1
;
}
else
{
//舍弃左侧
left=mid+
1
;
}
}
return
-
1
;
//查找失败 返回-1
}
/**
* @Title: bSearchRecursion
* 递归参数有不同，left和right明显在每次递归时都是变的
*/
public
static
int
binSearchRecursion(
int
[] arr,
int
left,
int
right,
int
des){
if
(arr==
null
|| arr.length<
1
){
return
-
1
;
}
if
(left<=right){
int
mid=left+(right-left)/
2
;
if
(des==arr[mid]){
return
mid;
}
else
if
(des<arr[mid]){
//舍弃右侧
return
binSearchRecursion(arr,left,mid-
1
,des);
}
else
{
//舍弃左侧
return
binSearchRecursion(arr,mid+
1
,right,des);
}
}
return
-
1
;
}
|
五、二分查找和斐波那契查找
折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，
同时为了防止溢出，使用更高效的移位，也可以记做 mid=low+((low+high)>>1)。
比较结果分三种情况
1）相等,mid位置的元素即为所求
2）> ,low=mid+1;
3）< ,high=mid-1;
斐波那契查找要求元素表中记录的个数为某个斐波那契数减1，即n=Fk-1;
斐波那契数列：0、1、1、2、3、5、8、13、21、……
如果设F(n）为该数列的第n项（n∈N）。那么这句话可以写成如下形式：
F(0) = 0，F(1)=1，F(n)=F(n-1)+F(n-2) (n≥2)，
这是一个线性递推数列，斐波那契数列的算法实现经常在数据结构教材的递归一节中出现。
对于二分查找，分割是从mid=(low+high)/2开始；而对于斐波那契查找，分割是从mid = low + F[k-1] - 1开始的； 通过上面知道了，数组a现在的元素个数为F[k]-1个，即数组长为F[k]-1，mid把数组分成了左右两部分， 左边的长度为：F[k-1] - 1， 那么右边的长度就为（数组长-左边的长度-1）， 即：（F[k]-1） - （F[k-1] - 1） = F[k] - F[k-1] - 1 = F[k-2] - 1。
斐波那契查找的核心是：
1）当key=a[mid]时，查找成功；
2）当key<a[mid]时，新的查找范围是第low个到第mid-1个，此时范围个数为F[k-1] - 1个，即数组左边的长度，所以要在[low, F[k - 1] - 1]范围内查找；
3）当key>a[mid]时，新的查找范围是第mid+1个到第high个，此时范围个数为F[k-2] - 1个，即数组右边的长度，所以要在[F[k - 2] - 1]范围内查找。
与二分查找相比，斐波那契查找它只涉及加法和减法运算，而不用除法（用“>>1”要好点）。因为除法比加减法要慢，在海量数据的查找过程中，这种细微的差别可能会影响最终的效率。
本文转自邴越博客园博客，原文链接：http://www.cnblogs.com/binyue/p/5219689.html，如需转载请自行联系原作者
