一、什么是查找？查找概述
在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。也就是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。
1. 查找概述
查找（Search）：是数据处理中最常见的一种操作，使用有关的查找算法在相应的存储表上查找出所需要的信息。
查找，就是在由一组记录组成的集合中寻找主关键字值等于给定值的某个记录，或是寻找属性值符号特定条件的某些记录。
查找定义：假设含n个记录的集合为{R0，R1，... ，Rn-1}，其相应的主关键字序列为{K0，K1，... ，Kn-1}，若给定某个主关键字K，查找就是在记录集合中定位满足条件Kj = K的记录的过程。
2. 查找表概述
查找表是一种以同一类型的记录构成的集合为逻辑结构，以查找为核心运算的数据结构。
查找表中常见的操作：
1. 建表
2. 查找：是指确定满足某种条件的记录是否在查找表中
3. 读表元：是指读取满足某种条件的记录的各种属性。
4. 对表做修改操作
查找表分为：静态查找表、动态查找表
1. 静态查找表：查找表的操作不包含对表的修改操作。也就是仅对查找表进行查找或读表元操作。
2. 动态查找表：若在查找的同时插入了表中不存在的记录，或从查找表中删除了已存在的记录。
3. 平均查找长度概述
平均查找长度（Average Search Length）：把查找过程中给定值与关键字值的比较次数的期望值作为衡量一个查找算法效率优劣的标准。
对一个含n条记录的查找表，查找成功时的平均查找长度为：
1. n是记录个数
2. pi是查找第i条记录的概率，且i=0时，p0=1，在每一个记录的查找概率相等的情况下，pi=1/n
3. ci是查找第i条记录时，关键字值与给定值比较的次数
二、静态表查找
1. 概述
静态查询表可以使用顺序表表示，也可以使用线性链表表示。本节中只讨论顺序表上的查找。
顺序表的查找有3种方式：
顺序查询
二分查找
分块查找
2. 顺序查找
1） 概述
顺序查找又称为线性查询，它是一种最简单、最基础的查找方法。
从顺序表的一端开始，依次将每一个数据元素的关键字值与给定值key进行比较，
若某个数据元素的关键字值等于给定值key，则表明查询成功
若直到所有数据元素都比较完毕，仍找不到关键字值为key的数据元素，则表明查找失败。
2）算法分析
假设顺序查找的基本要求是：从顺序表r[0]到r[n-1]的n个数据元素中，顺序查找出关键字值为key的记录，
若查询成功，则返回其下标；
否则，返回-1.
3）算法：顺序查找
1.代码
//【算法】顺序查找 public int seqSearch(Comparable key) { int i = 0 , n = length(); while(i < n && r[i].key.compareTo(key) != 0) { i++; } if(i < n) { return i; } else { return -1; } }
2. 测试
public class TestSeqSearchList1_seqSearch { public static void main(String[] args) throws Exception { int[] arr = {52,39,67,95,79,8,25,52}; SeqSearchList seqSearchList = new SeqSearchList(arr.length); for (int i = 0; i < arr.length; i++) { seqSearchList.insert(i, new RecordNode(arr[i])); } //顺序查找 int i = seqSearchList.seqSearch(39); System.out.println(i); } }
4）算法：带监视哨的顺序查找
代码
//【算法】带监视哨的顺序查找 // 从顺序表r[1]到r[n]的n个数据元素中顺序查找出关键字值为key的数据元素 // 若查找成功，则返回其下标，否则，返回-1 public int seqSearchWithGuard(Comparable key) { int i = length() - 1; r[0].key = key; while(r[i].key.compareTo(key) != 0) { i--; } if(i > 0) { return i; } else { return -1; } }
测试
public class TestSeqSearchList2_seqSearchWithGuard { public static void main(String[] args) throws Exception { int[] arr = {0,52,39,67,95,79,8,25,52}; SeqSearchList seqSearchList = new SeqSearchList(arr.length); for (int i = 0; i < arr.length; i++) { seqSearchList.insert(i, new RecordNode(arr[i])); } //带监视哨的顺序查找 int i = seqSearchList.seqSearchWithGuard(95); System.out.println(i); } }
5）性能分析
==改进后==的顺序查找算法（共有n+1条记录，0为监视哨），要查找到第i条记录，需要与关键字值的比较次数为n-i+1，在等概率下
顺序查找的时间复杂度为O(n)，当n较大时，查找效率较低。
顺序查找的优点是既适用于顺序表，也适用于单链表。
同时对表中数据元素的排列次序无任何要求，这将给在表中插入新的数据元素带来方便。因为不需要在插入新的数据元素时，寻找插入位置和移动原有的数据元素，只要把它们添加到表尾(对于顺序表)或表头(对于单链表)即可。
3、二分查找
1）概述
顺序查找表上的查找算法虽然实现简单，但平均查找长度较大。不适合用于表长较大的查找表。
若以有序表表示静态查找表，通过二分查询，可以缩短平均查找长度。
二分查询（binary search）
二分查询前提：
1. 数据必须是顺序存储的有序表
2. 且关键字按从小到大排列
3. 关键字值为数值，则按数值有序
4. 关键字值为字符数据，则按对应Unicode码有序
二分查找基本思想：
1. 首先取整个有序表的中间记录的关键字值与给定值相比较
2. 若相等，则查询成功
3. 否则，以位于中间位置的数据元素为分界点，将查找表分成左右两个子表，并判断待查找的关键字值key是在左子表还是在右子表，再在左或右子表中重复上述步骤
4. 直到找到关键字值为key的记录或子表长度为0
2）算法分析
基本要求：有序表{r[0], r[1], ..., r[n-1]}中查找关键字值为key的记录，
若查询成功，则返回其下标；否则，返回-1
需要变量
low：待查询区域的第一条记录数组下标
high：待查询区域的最后一条记录数组下标
mid：待查询区域的中间记录数组下标
步骤：
置初值：low=0 , high=n-1
当 low ≤ high时，重复执行下列步骤：
mid = (low + high) / 2
若key与r[mid]的关键字相等，则查找成功，返回mid值，否则
若key小于r[mid]的关键字值，则high = mid - 1；否则 low = mid + 1
当 low＞high 时，查询失败，返回-1
3）算法：二分查找
代码
//【算法】二分查找算法 public int binarySearch(Comparable key) { if(length() > 0) { int low = 0, high = length() - 1; // 查找范围的下界和上界 while (low <= high) { int mid = (low + high) / 2; // 中间位置，当前比较的数据元素位置 System.out.println("mid:" + mid); if(r[mid].key.compareTo(key) == 0) { return mid; // 查询成功 } else if (r[mid].key.compareTo(key) > 0) { // 中间值比给定值大 high = mid - 1; // 查找范围缩小到前半段 } else { low = mid + 1; // 查询范围缩小到后半段 } } } return -1; // 查询失败 }
测试
public class TestSeqSearchList3_binarySearch { public static void main(String[] args) throws Exception { int[] arr = {12,23,26,37,54,60,68,75,82,96}; SeqSearchList seqSearchList = new SeqSearchList(arr.length); for (int i = 0; i < arr.length; i++) { seqSearchList.insert(i, new RecordNode(arr[i])); } //带监视哨的顺序查找 // int i = seqSearchList.binarySearch(23); // int i = seqSearchList.binarySearch(96); int i = seqSearchList.binarySearch(58); System.out.println("查询结果：" + i); } } // 查找关键字：23 //mid:4 //mid:1 //查询结果：1 // 查找关键字：96 //mid:4 //mid:7 //mid:8 //mid:9 //查询结果：9 // 查找关键字：58 //mid:4 //mid:7 //mid:5 //查询结果：-1
4）性能分析
二分查找每经过一次比较就将待查找区域缩小一半，因此，比较次数是log2n
假设n=2k-1结点，线性表至多被平分k次即可完成查找。
二分查找的平均查找长度：ASL ≈ log2(n+1) - 1
二分查找比顺序查找快的多，但要求线性表必须按关键字排序，排序的最佳时间复杂度 O(nlog2n)
线性表的二分查找仅适用于顺序存储结构，不适用于动态查询表（顺序存储的插入、删除等运算不方便）
4、分块查找
1）概述
分块查找又称为索引顺序查找，它是顺序查找法与二分法的一种结合。
基本思想：
首先把线性表分成若干块，在每一块中，结点的存放不一定有序，但块与块之间必须是有序的
假定按结点的关键字值递增有序，则第一块中结点的关键字值都小于第二块中任意结点的关键字值，第二块中的结点的关键字值都小于第三块中任意结点的关键字值，依次类推，
最后一块中所有结点的关键字值大于前面所有块中结点的关键字值。
2）算法分析
分块查询实现
创建一个索引表，将每一块中最大的关键字值按块的顺序存放在一个索引顺序表中，显然这个索引顺序表时按关键字值的递增排列的。
查找时，首先通过索引表确定待查找记录可能所在的块，然后再在所在的块内查找待查找的记录。
由于索引表是按关键字有序，则确定块的查找可以采用顺序查找，也可以采用二分查找
由于每一块中记录是无序的，则在块内只能采用顺序查找方法。
3）性能分析
将长度为n的线性表平均分为b块，每块中含有s个记录，则 b = ⌈ n / s ⌉
每一个记录的查找概率相等，则每块查找的概率 1/b，块中每个记录的查找概率为 1/s
ASL ≈ log2(n/s + 1) + s / 2
