一.顺序查找
1.1 思路：这是最简单的算法，从头开始遍历每个元素，并将每个元素与查找元素比较，如果一致则返回。
1.2 时间复杂度: O(N)
1.3 空间复杂度: O(1)
1.4 代码：
public int search(int[] array, int num) {
if(array == null || array.length == 0) {
return -1;
}
for(int i = 0; i < array.length; i++) {
if (array[i] == num) {
return i;
}
}
return -1;
}
二.二分查找
2.1 思路：二分查找前提是查找的数组是有序的，利用数据有序的特性提高查找性能。首先与数组中间位置的值比较，如果查找值大于中间位置值，则对数组右边以相同的思路查找，否则在左边以相同方式查找。这种方式使得每次查找范围变为原来的1/2.
2.2 时间复杂度：O(log2n)
2.3 空间复杂度: O(1)
public int halfSearch(int[] array, int num) {
if(array == null || array.length == 0) {
return -1;
}
int lo = 0, hi = array.length-1;
while(lo <= hi) {
int mid = (lo + hi) >> 2;
if (array[mid] == num) {
return mid;
} else if (array[mid] < num) {
hi = mid -1;
} else {
lo = mid + 1;
}
}
return -1;
}
这里有道题，两个有序数组，长度分别为n和m，求其中位数，要求时间复杂度为log(m+n)
如，a = {1,2,3};b = {3,4,5}; 其中位数是 3
a= {1,2};b={3,4};中位数 （2+3）/2 = 1.5
思路，这两个数组的中位数比较，因为两个数组一起的中位数一定在这两个数组各自的中位数中间，这样每次可以去除一半的数据。
三. 变种二分查找
http://www.cr173.com/html/20428_1.html
四. hash 算法
4.1 思想：哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映射到一个有限的地址区间上，并将关键字对应的值存储在该地址空间，可以通过关键字快速获取对应的值，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。
4.2 查找复杂度: O(1)
4.3 哈希函数：
- 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）
- 数字分析法：因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。
- 平方取中法：取关键字平方后的中间几位作为散列地址
- 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
- 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
4.4 hash冲突及解决
hash冲突在所难免，解决冲突是一个复杂问题。冲突主要取决于：
（1）与散列函数有关，一个好的散列函数的值应尽可能平均分布。
（2）与解决冲突的哈希冲突函数有关。
（3）与负载因子的大小。太大不一定就好，而且浪费空间严重，负载因子和散列函数是联动的。
解决冲突的办法：
（1）开放定址法：线性探查法、平方探查法、伪随机序列法、双哈希函数法。
（2) 拉链法：把所有同义词，即hash值相同的记录，用单链表连接起来。
4.5 应用：
1.字符串哈希
2.加密哈希
3.几何哈希
4.布隆过滤器
4.6 不足：获取有序序列复杂度高
参考：
http://www.tuicool.com/articles/RnErui
5.1子字符串查找
- 暴力字符串查找算法
- KMP算法(建议看下面链接的博文，图文形象，很好理解)
http://www.cnblogs.com/c-cloud/p/3224788.html
字符串S的最长回文子串S1
思想：KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，只要继续把它向后移和移动匹配词就可以，这样就提高了效率。可以针对搜索词，算出一张部分匹配表。通过查表查到最后一个匹配字符对应的部分匹配值，并利用以下公式计算匹配词向后移动的位数：
移动位数 = 已匹配的字符数 - 对应的部分匹配值
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
- "A"的前缀和后缀都为空集，共有元素的长度为0；
- "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
- "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
- "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
- "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
- "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
- "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
实现：
/**
* 计算部分匹配表
*
* @param pattern
* @param next
*/
public void makeNext(char[] pattern, int next[]) {
int pIdx, maxSuffixLen; // pIdx:模版字符串下标；maxSuffixLen:最大前后缀长度
int m = pattern.length; // 模版字符串长度
next[0] = 0; //模版字符串的第一个字符的最大前后缀长度为0
for (pIdx = 1, maxSuffixLen = 0; pIdx < m; ++pIdx) //for循环，从第二个字符开始，依次计算每一个字符对应的next值
{
/**
* maxSuffixLen 大于0 表示前一个字符已经存在匹配
*/
while (maxSuffixLen > 0 && pattern[pIdx] != pattern[maxSuffixLen]) { //递归的求出P[0]···P[q]的最大的相同的前后缀长度k
maxSuffixLen = next[maxSuffixLen - 1]; //不理解没关系看下面的分析，这个while循环是整段代码的精髓所在，确实不好理解
}
if (pattern[pIdx] == pattern[maxSuffixLen]) //如果相等，那么最大相同前后缀长度加1
{
maxSuffixLen++;
}
next[pIdx] = maxSuffixLen;
}
}
public int kmp(String str, String pattern) {
int[] next = new int[str.length()];
int strIdx, pIdx;
makeNext(pattern.toCharArray(), next);
for (strIdx = 0, pIdx = 0; strIdx < str.length(); ++strIdx) {
while (pIdx > 0 && pattern.charAt(pIdx) != str.charAt(strIdx)) {
/**
* 移动匹配字符串位置
*/
pIdx = next[pIdx - 1];
}
if (pattern.charAt(pIdx) == str.charAt(strIdx)) {
pIdx++;
}
if (pIdx == pattern.length()) {
return strIdx - pattern.length() + 1;
}
}
return -1;
}
复杂度：时间复杂度最坏（3N） 空间复杂度 O(M）
