查找

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素

概论

查找表：由同一类型的数据元素（或记录）构成的集合

关键字：数据元素中某个数据项的值

若此关键字可以唯一地标识一个记录，则称此关键字为主关键字

可以识别多个数据元素（或记录）的关键字，我们称为次关键字

静态查找表（Static Search Table）：只作查找操作的查找表

动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

顺序表查找

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功

有序表查找

折半查找

折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。

折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止

插值查找

插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法

对于分布比较均匀的查找表会好些，但是极端数据会比较难处理

斐波那契查找

线性索引查找

数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构

索引：把一个关键字与它对应的记录相关联的过程

线性索引：将索引项集合组织为线性结构，索引表

稠密索引

指在线性索引中，将数据集中的每个记录对应一个索引项，索引项一定是按照关键码有序的排列

分块索引

分块有序，是把数据集的记录分成了若干块

对细分块不需要有序

倒排索引

倒排索引源于实际应用中需要根据属性（或字段、次关键码）的值来查找记录

这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地

二叉排序树

即左边小，右边大

构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度

二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可

平衡二叉树AVL树

是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1

在遇到不平衡时，可以采用左旋或者右旋的形式

平衡二叉树的时间复杂度为O(log），是比较理想的动态查找表算法

多路查找树

每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。

以下知识可以参考树

散列表查找（哈希表）

定义

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）

采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。

查找步骤

散列技术既是一种存储方法，也是一种查找方法

其最适合的求解问题是查找与给定值相等的记录

构造方法

1. 直接定址法：取关键字的某个线性函数值为散列地址
2. 数字分析法：对抽取出来的数字进行操作
3. 平方取中法
4. 折叠法
5. 除留余数法
6. 随机数法

二分查找

首先确定好两边的长度，找到中间值，然后判断与target是否相等，不想等的话判断大小之后进入左或者右边，接着判断

    int search(vector<int>& nums, int target) {        // write code here        int l=0;        int r = nums.size() -1;        while(l <= r){            int m = (l+r)/2;            if(nums[m] == target)                return m;            else if (nums[m] > target)                r = m-1;            else                l = m+1;        }        return -1;    }};

二维数组中的查找

1. 暴力搜索的方式：全都遍历一遍，最坏的情况全都要遍历

class Solution {public:    bool Find(int target, vector<vector<int> > array) {       for(auto i : array)//c++11语法        {            for(auto j : i)            {                if(j == target) return true;//找到目标值            }        }        return false;//未找到    }};

1. 利用二分搜索的方式，拆成每一行都用二分搜索，这样可以减少部分时间复杂度，在单行搜索中减少了

class Solution {public:    bool binary_search(vector<int> arr,int target){//二分查找函数        int left = 0,right = arr.size()-1;               while(left<=right)                {                    int mid = (left+right)/2;                    if(arr[mid] == target) return true;//找到了                    else if(arr[mid] < target) left = mid+1;//往右边遍历                    else right = mid-1;//往左边遍历                }                return false;        }    bool Find(int target, vector<vector<int> > array) {        for(auto i : array)//c++11语法，逐行遍历；        {            if(binary_search(i,target)) return true;//在本行二分找到了目标值        }        return false;   }};

1. 利用已经排好序的特点，下一行总是比上一行的大，右边总是会比左边的大，所以可以从最左下角点开始，逐个判断，但是判断的过程中并不是所有遍历，而是隔着几个，时间复杂度会更低

class Solution {public:    bool Find(int target, vector<vector<int> > array) {        if(array.size() == 0)  return false;        int r = array.size(); //行        int l = array[0].size(); //列        int left = 0, down = r - 1;        while(left<l && down>=0)        {            int tmp = array[down][left];            if( tmp == target) return true;            else if(tmp < target) left++;            else down--;        }        return false;    }};

1. 双二维查找，把上下左右都分开两部分来进行比较

class Solution {public:    bool double_binary(vector<vector<int>> arr,int x1,int x2,int y1, int y2,int target){        if(x1 == x2 || y1 == y2) return false;        int xmid = (x1+x2)/2, ymid = (y1+y2)/2;        int num = arr[xmid][ymid];        if(num == target) return true;        if(num > target)        {           if(double_binary(arr, x1, xmid, y1, y2, target)) return true;           if(double_binary(arr,xmid,x2,y1,ymid,target)) return true;        }        else        {            if(double_binary(arr, xmid+1, x2, y1, y2, target)) return true;            if(double_binary(arr, x1, xmid+1, ymid+1, y2, target)) return true;        }        return false;    }    bool Find(int target, vector<vector<int> > array) {        if(array.size() == 0) return false;        return double_binary(array, 0, array.size(), 0, array[0].size(), target);    }};