数据结构复习6-拓冰建站

第七章查找

折半查找（二分查找）

仅适用于有序的顺序表

迭代实现

public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2; // 防止溢出，等同于(left + right)/2if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1; // 未找到}

递归实现

 public static int binarySearch(int[] arr, int left, int right, int target) {if (left > right) {return -1;}int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {return binarySearch(arr, mid + 1, right, target);} else {return binarySearch(arr, left, mid - 1, target);}}

分块查找

分块查找针对的情况：块内无序、块间有序。

分块查找（Block Search）又称索引顺序查找，是介于顺序查找和二分查找之间的一种查找方法。它将数据分成若干块，块内元素可以无序，但块间有序（即后一块中所有元素均大于前一块中所有元素）。

代码：

 // 块结构static class Block {int max;        // 块内最大值int startIndex;  // 块起始索引int endIndex;    // 块结束索引public Block(int max, int startIndex, int endIndex) {this.max = max;this.startIndex = startIndex;this.endIndex = endIndex;}}public static int blockSearch(int[] arr, List<Block> blocks, int target) {// 1. 先在索引表中确定目标值可能所在的块Block targetBlock = null;for (Block block : blocks) {if (target <= block.max) {targetBlock = block;break;}}// 如果所有块的最大值都小于目标值，则目标值不存在if (targetBlock == null) {return -1;}// 2. 在确定的块内进行顺序查找for (int i = targetBlock.startIndex; i <= targetBlock.endIndex; i++) {if (arr[i] == target) {return i;}}return -1; // 未找到}

散列表

平均查找长度（ASL）：散列表查找成功的平均查找长度即找到表中已有表项的平均比较次数；散列表查找失败的平均查找长度即找不到待查的表项但能找到插入位置的平均比较次数。

一些面试题

7.1 如何从海量数据里找到最大的10000个数（top K问题）？

方法一：建最小堆，先拿10000个数建最小堆，然后依次添加剩余元素，如果大于堆顶的数（10000中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆，这样，遍历完后，堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O（mlogm），算法的时间复杂度为O（nmlogm）（n为10亿，m为10000）。

方法二：用分块查找（找相对大的数，而非一定是最大的10000个数），可以把所有10亿个数据分组存放，比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起在再找出最终的结果。

7.2 哈希函数的构造方法及解决冲突的方法

构造方法：

直接定址法
除留余数法
数字分析法
平方取中法

解决冲突：

1）开放定址法：

        1.1 线性探测法

        1.2 平方探测法

        1.3 双散列法

        1.4 伪随机序列法

2）拉链法：

29. 介绍一下哈希表，如何构造哈希函数，如何解决哈希冲突？★★★★

哈希表又称为散列表，是根据关键字的值直接进行访问的数据结构，即它通过把关键码的值映射到表中的一个位置以加快查找速度，其中映射函数叫做哈希函数，存放记录的数组叫做哈希表。

（1）哈希函数的构造方法：

① 直接定址法：

取关键字的某个线性函数值作为散列地址，H(key)=a*key+b。

② 除留余数法：

取关键字对p取余的值作为散列地址，即H(key)=key%p，p尽量选择质数，为了使散列分布更均匀。

（2）哈希冲突的解决方法：

① 开放地址法：

当发生冲突时，使用一定的探测序列方法，在哈希表中寻找下一个可用的空槽位，将冲突的元素插入到这个空槽位中。常见的探测序列方法有线性探测、二次探测等。

② 链地址法

将哈希表的每个索引位置看作一个链表的头节点，当发生冲突时，将冲突的元素插入到链表中即可。这样，每个索引位置都可以存储多个元素。

③ 再哈希法

当发生冲突时，使用另一个哈希函数重新计算新的索引位置，直到找到一个空槽位来解决冲突。