二分查找
二分查找又叫折半查找,是在有序列表的基础上进行查找,每次查找可以筛掉一半的元素。
算法步骤
以升序数列$L[0…n-1]$为例,假设要查找的数为$x$:
让$x$与数列中间位置的元素$L[\lfloor \frac n2 \rfloor]$进行比较,如果相等则返回该元素下标,否则:
- 如果$x$比中间元素小,递归地对中间元素左边的数列(比二分查找小的元素)进行二分查找;
- 如果$x$比中间元素大,递归地对中间元素右边的数列(比二分查找大的元素)进行二分查找。
代码实现
Python实现
- 递归实现:
def BinarySearch(arr, target, left = 0, right = 0): """二分排序(递归实现) left=0,right=len(arr)-1""" if left == 0 and right == 0: right = len(arr)-1 if left > right or len(arr) == 0: return -1 mid = int((left + right) / 2) if target == arr[mid]: return mid elif target < arr[mid]: return BinarySearch(arr, target, left, mid-1) else: return BinarySearch(arr, target, mid+1, right) if __name__ == "__main__": arr = list(range(100)) target = 66 result = BinarySearch(arr, target) if result == -1: print(False) else: print(result)
- 非递归实现:
def BinarySearch(arr, target): """二分排序(非递归实现)""" if len(arr) == 0: return -1 left = 0 right = len(arr)-1 while left <= right: mid = int((left + right) / 2) if target == arr[mid]: return mid elif target < arr[mid]: right = mid - 1 else: left = mid + 1 return -1 if __name__ == "__main__": arr = list(range(100)) target = 66 result = BinarySearch(arr, target) if result == -1: print(False) else: print(result)
C实现
- 递归实现:
#include <stdio.h> #define LEN 100 int BinarySearch(int arr[], int left, int right, int target) { if (left > right || arr == NULL) return -1; int mid = (left + right) / 2; if (target == arr[mid]) return mid; else if (target < arr[mid]) return BinarySearch(arr, left, mid-1, target); else return BinarySearch(arr, mid+1, right, target); } int main(void) { int arr[LEN]; for (int i = 0; i < LEN; i++) arr[i] = i; int target = 66; int result = BinarySearch(arr, 0, LEN-1, target); if (result == -1) printf("False\n"); else printf("%d\n", result); return 0; }
- 非递归实现:
#include <stdio.h> #define LEN 100 int BinarySearch(int arr[], int left, int right, int target) { if (left > right || arr == NULL) return -1; while (left <= right) { int mid = (left + right) / 2; if (target == arr[mid]) return mid; else if (target < arr[mid]) right = mid - 1; else left = mid + 1; } return -1; } int main(void) { int arr[LEN]; for (int i = 0; i < LEN; i++) arr[i] = i; int target = 66; int result = BinarySearch(arr, 0, LEN-1, target); if (result == -1) printf("False\n"); else printf("%d\n", result); return 0; }
散列表查找
散列表查找又叫哈希表查找,是通过记录存储位置和关键字构建一个确定的关系$f$,使得每个关键字$key$对应一个存储位置$f(key)$,称这个为散列技术。其中,$f$称为散列函数或者哈希函数。
通过散列技术将记录存储在一块连续的存储空间中,这块连续的空间称为散列表或者哈希表。
散列表最适合查找与给定的值相等的记录。
散列函数的冲突:
在使用散列表的过程中,可能会有两个关键字通过散列函数得到的存储地址是一样的,这个现象被称为冲突。此时就需要通过冲突解决办法来解决冲突。在解决冲突的同时也要保证查找和插入效率问题。同时为了避免冲突,散列函数的构造也是很重要的。
算法步骤
散列函数的构造方法
选取散列函数的参考:
- 计算散列地址所需的时间;
- 关键字长度;
- 散列表大小;
- 关键字的分布情况;
- 查找记录的频率。
直接定址法
直接定址法就是直接通过取关键字的某个线性值作为散列地址:
$$ f(key)=a \cdot key+b\quad(a,b为常数) $$
例如,要存储0-100岁的人口统计表,就可以采用散列函数为:
f(key) = key
数字分析法
数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布比较 均匀,就可以考虑这个方法。
Example:
假设某公司的员工登记表以员工的手机号作为关键字。手机号一共11位。前3位是接入号,对应不同运营商的子品牌;中间4位表示归属地;最后4位是用户号。不同手机号前7位相同的可能性很大,所以可以选择后4位作为散列地址,或者对后4位反转(1234 -> 4321)、循环右移(1234 -> 4123)、循环左移等等之后作为散列地址。
平方取中法
假设关键字是1234,平方之后是1522756,再抽取中间3位227,用作散列地址。平方取中法比较适合于不知道关键字的分布,而位数又不是很大的情况。
折叠法
将关键字从左到右分割成位数相等的几部分,最后一部分位数不够时可以短些,然后将这几部分叠加求和, 并按散列表表长,取后几位作为散列地址。
比如关键字是9876543210,散列表表长是3位,将其分为四组,然后叠加求和:987 + 654 + 321 + 0 = 1962,取后3位962作为散列地址。
折叠法事先不需要知道关键字的分布,适合关键字位数较多的情况。
除留取余数法
此方法为最常用的构造散列函数方法。
除留取余数法:
$$ f(key)=key\enspace mod\enspace p\quad (p\le m),\ m为散列表长 $$
这种方法不仅可以对关键字直接取模,也可在折叠、平方取中后再取模。根据经验,若散列表表长为$m$,通常$p$为小于或等于表长(最好接近$m$)的最小质数,可以更好的减小冲突。
随机数法
$$ f(key)=random(key),\quad random是随机函数 $$
当关键字的长度不等时,采用这个方法构造散列函数是比较合适的。
处理散列表冲突问题的方法
开放地址法
开放地址就是一旦发生冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并且记录它。有三种寻找空散列地址的方法:
-
线性探测法
$$ f’(key)=(f(key)+d)% n,\quad 其中d取(0,1,2,…,n-1),\ n为散列表的长度 $$
$d$初始为0,如果有冲突,那么$d$就通过递增来寻找空的散列地址。
Example:
下标 0 1 2 3 4 5 6 7 8 9 10 11 关键字 12 25 16 67 56 在如上所示的散列表中插入37。首先使用散列函数计算37的散列地址:$f’(37)=f(37)%12=1$(这里假设$f(key)=key$)。 而下标为1的位置已经存放了25,那就只能继续寻找下一个空散列地址:$f’(37)=(f(37)+1)%12=2$。
2这个位置没有内容,所以得到:
下标 0 1 2 3 4 5 6 7 8 9 10 11 关键字 12 25 37 16 67 56 使用线性探测来解决冲突问题,会造成冲突堆积。所谓的冲突堆积就是上例的37,它本来是属于下标1的元素,现在却占用了下标为2的空间。如果现在需要存放原本存放在下标为2的元素,就会再次发生冲突,这个冲突会一直传播下去,大大减低查找和插入效率。 -
二次探测法
$$ f’(key)=(f(key)+q^2)%n,\quad 其中q取(0,1,-1,2,-2,…,\frac n2,-\frac n2),\ n为散列表的长度 $$
二次探测法其实是对线性探测的一个优化,增加了平方可以不让关键字聚集在某一块区域。
Example:
下标 0 1 2 3 4 5 6 7 8 9 10 11 关键字 12 25 37 16 67 56 插入元素7,通过二次探测的散列函数计算得到:$f’(7)=f(7)%12=7$。 但下标为7的位置已经存放了67,所以需要寻找下一个存储地址:$f’(7)=(f(7)+1^2)%12=8$。
下标为8的位置已经存放了56,继续寻找: $f’(7)=(f(7)+(-1^2))%12=6$。
6这个位置为空,得到:
下标 0 1 2 3 4 5 6 7 8 9 10 11 关键字 12 25 37 16 7 67 56 -
随机探测法
$$ f’(key)=(f(key)+d)%m,\quad d为随机数,m为表长 $$
在实现中应预先用随机数发生器产生一个随机序列,将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序,从而可以避免或减少堆积。
多重散列法
多重散列法又叫再散列函数法。其公式如下:
$$ f’(key)=RH(key) $$
其中$RH$就是不同的散列函数,这些散列函数可以是任何散列函数。只要其中一个发生了冲突,就马上换一个散列函数,直到冲突解决。缺点就是增加了很多计算时间。
链地址法
链地址法就是当冲突发生时,用链表来存放同义词(即存放在当前位置,每个位置使用链表存放同义词)。这个思路和图的邻接表存储方式很相似。
公共溢出区法
公共溢出区法就是把那些冲突的元素直接追加到另外一个溢出表中,如下图所示:
在查找的时候,如果在基本表没有找到,那么就只能去溢出表中进行顺序查找。这个方法比较适合冲突元素少的情况。
代码实现
Python实现
- 除留取余数法构造散列函数,开放地址法-线性探测处理散列表冲突:
class HashTable: def __init__(self, size): self.elem = [None for i in range(size)] self.size = size def hash(self, key): """除留取余数法构造哈希函数""" return key % self.size def insert_hash(self, key): address = self.hash(key) # 开放地址法-线性探测 while self.elem[address]: address = (address+1) % self.size self.elem[address] = key def search_hash(self, key): star = address = self.hash(key) while self.elem[address] != key: address = (address + 1) % self.size if not self.elem[address] or address == star: return -1 return address if __name__ == "__main__": list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34] hash_table = HashTable(12) for i in list_a: hash_table.insert_hash(i) for i in hash_table.elem: if i: print((hash_table.elem.index(i), i), end=" ") print("") print(hash_table.search_hash(15)) print(hash_table.search_hash(33))
评论