查找算法

英文介绍 https://www.tutorialspoint.com/data_structures_algorithms/binary_search_algorithm.htm

1. 线性查找

原理：对所有元素逐个进行顺序搜索，如果找到匹配项，则返回该元素，否则将继续搜索，直到数据收集结束。

2. 二分查找

条件：线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
原理：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较
      如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表
      如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表
      重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功
举例：查找数字31

升序排列数组
折半定位27
舍弃前半段
继续折半定位35
舍弃后半段
折半定位31
中

3. 插值查找

基本原则等同于二分查找，只不过中间值是透过比例运算得来
mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
where −
A = list
Lo = Lowest index of the list
Hi = Highest index of the list
A[n] = Value stored at index n in the list

4. Hash Table

哈希：是一种将一系列键值转换为数组的一系列索引的技术
哈希表：是以关联方式存储数据的数据结构。
        在哈希表中，数据以数组格式存储
        其中每个数据值都有自己的唯一索引值。
        如果我们知道所需数据的索引，数据的访问就会变得非常快。