常用查找算法（Java）

2018-01-22

 

1 顺序查找

就是一个一个依次查找

2 二分查找

二分查找（Binary Search）也叫作折半查找。

二分查找有两个要求，

• 一个是数列有序，
• 另一个是数列使用顺序存储结构（比如数组）。

/** * 二分查找 */public class BinarySearch {    public static void main(String[] args)    {        int[] arr=new int[]{1,2,3,5,6,6,8,9};        BinarySearch binarySearch=new BinarySearch(arr);        System.out.println(binarySearch.searchRecursion(5));        System.out.println(binarySearch.searchRecursion(4));        System.out.println(binarySearch.searchRecursion(6));        System.out.println(binarySearch.search(5));        System.out.println(binarySearch.search(7));        System.out.println(binarySearch.search(6));    }    private int[] arr;    public BinarySearch(int[] arr)    {        this.arr=arr;    }    public int searchRecursion(int target)    {       return searchRecursion(target,0,arr.length-1);    }    private int searchRecursion(int target,int begin,int end)    {        if(begin<=end)        {            int mid=(begin+end)/2;            if(arr[mid]==target) return mid;            if(arr[mid]>target)                return searchRecursion(target,begin,mid-1);           else                return searchRecursion(target,mid+1,end);        }        return -1;    }    private int search(int target)    {        int begin =0;        int end=arr.length-1;        while(begin<=end)        {            int mid=(begin+end)/2;            if(arr[mid]==target) return mid;            if(arr[mid]>target) end=mid-1;            else begin=mid+1;        }        return -1;    }}

3 分块查找

分块查找是结合二分查找和顺序查找的一种改进方法。在分块查找里有索引表和分块的概念。索引表就是帮助分块查找的一个分块依据。分块查找只需要索引表有序。

分块查找有点类似于哈希表，但又不如散列表好用，其实很多时候我们在编程中并不会直接用到这个算法，但是分块的思想在很多时候还是很有用的。

public class BlockSearch {    public static void main(String[] args) {        int[] index = new int[]{10, 20, 30};        BlockSearch blockSearch = new BlockSearch(index);        blockSearch.insert(-1);        blockSearch.insert(10);        blockSearch.insert(25);        //blockSearch.insert(31);        blockSearch.search(0);        blockSearch.search(-1);        blockSearch.search(10);        blockSearch.search(25);    }    private int[] index;    private ArrayList[] list;    public BlockSearch(int[] index) {        if (index != null && index.length != 0) {            this.index = index;            list = new ArrayList[index.length];            for (int i = 0; i < list.length; i++) {                list[i] = new ArrayList();            }        } else {            throw new Error("index cannot be null or empty.");        }    }    public void insert(int data) {        int i = binarySearch(data);        list[i].add(data);    }    public void search(int data) {        int i = binarySearch(data);        for (int j = 0; j < list[i].size(); j++) {            if (data == (int) list[i].get(j)) {                System.out.println(String.format("'%d' Position: [%d,%d]", data, i, j));                return;            }        }        System.out.println(String.format("'%d' Position: Not found", data));    }    private int binarySearch(int data) {        if(data>index[index.length-1])            throw new Error("out of block range");        int start = 0;        int end = index.length - 1;        int mid;        while (start < end) {            mid = (start + end) / 2;            if (index[mid] > data) end = mid - 1;            else                //如果相等，也插入后面 <=index[start]                start = mid + 1;        }            return start;    }}

4 搜索引擎与倒排索引

搜索引擎就是从大量的数据中根据关键字查找出对应的信息。搜索引擎之所以能够快速地根据我们键入的关键字获取结果列表，这都是索引的功劳。

索引分为倒排索引和正排索引，我们用到的一般都是倒排索引。

倒排索引的英文是Inverted Index。比如有一个文档列表，每个文档都会有唯一的ID，我们建立关键字和文档id的索引表即可。

倒排索引的关键字提取，对于英文比较容易，可以以单词分割；对于中文就比较复杂，不同的字组成的词很多。比如“中华人民共和国”这个词可以是一个词，“中华”也可以是一个词，并分出其他好多词。