查找算法以及字符串查找

一.顺序查找

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 哈希函数：

1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）
2. 数字分析法：因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。
3. 平方取中法：取关键字平方后的中间几位作为散列地址
4. 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
5. 除留余数法：取关键字被某个不大于散列表表长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）