七大查找算法

顺序查找

• 原理：如果是一个小孩子要去找一个东西，那么他大概率会一个一个去找。

• 模版要点：

  def 顺序查找(被查列表,查找目标):
    for 第i个数 in range(0,被查列表长度):
        if(被查列表[第i个数]==查找目标):
            return 第i个数
    return -1   
  

  当被查列表有序时可以使用的优化：

  1. 当查找的数大于目标数时，可以直接返回-1。不用再查后面的了
  2. 跳表：不一个一个的查找，多个多个的查找当查找的数大于目标数时，再返回看一下。这里要注意跳出边界的情况(直接返回查)

---

二分查找(有序)

• 原理：在有序表中,取中间的一个数将列表分成两半。根据(中间的数和查找目标)判断左边和右边哪边不符合，将不符合的一边的指针移动到中间的这个下标(相当于一次比较就排除了一半的错误结果)。然后用新的左右指针算新的列表的中间数。重复该步骤。

• 模版要点：

  1. 元素必须是有序的，如果是无序的则要先进行排序操作
  2. 左边有效的查找数下标+1!=右边有效的查找数下标: 判断的是是否

  def 二分查找(有序被查列表,查找目标):
     左边有效的查找数下标=-1
     右边有效的查找数下标=有序被查列表长度
       while 左边有效的查找数下标+1!=右边有效的查找数下标:
            有效范围列表中间数_在有序被查列表中的下表=parsrInt((左边有效的查找数下标+右边有效的查找数下标)/2)
            if 有序被查列表(有效范围列表中间数_在有序被查列表中的下表)&查找目标: #判断左边和右边的列表哪个符合结果
                左边有效的查找数下标=有效范围列表中间数_在有序被查列表中的下表 #当左边不满足时
            else:
                右边有效的查找数下标=有效范围列表中间数_在有序被查列表中的下表 #当右边不满足时
       return 左边有效的查找数下标|右边有效的查找数下标 #当左右指针相邻时返回对应的目标下标
  

---

插值查找(有序)

• 原理：当在查找词典的单词的时候，比如查找search这个单词，我们会在词典索引的s部分查找。然后再在s部分使用上面的二分查找。

• 模版要点：

  用二分查找法查s范围
  # 基于二分查找模板的，将二分查找模板的初始有效指针指向s范围即可。
  左边有效的查找数下标=s开头下标-1
  右边有效的查找数下标=s开头下标结尾下标+1
  

---

斐波那契查找(有序)

• 原理：斐波那契数列：f(1)=1;f(2)=1;f(n)=f(n-1)+f(n-2)

---

树表查找-二叉树(上面的属于静态查找，)

• 原理：链式结构，

• 模版要点：

---

树表查找-平衡二叉树(上面的属于静态查找，)

• 原理：链式结构，

• 模版要点：

---

树表查找-B-树(上面的属于静态查找，)

• 原理：链式结构，

• 模版要点：

---

树表查找-B+树(上面的属于静态查找，)

• 原理：链式结构，

• 模版要点：

---

分块查找(半有序)

• 原理：作用于块外有序，块内有序的列表
  相当于需要用有序算法，查具体去那个块查找。然后用顺序查找查具体块

• 模版要点：

  1. 索引表是存储每个块最大的值的列表
  2. 索引表的对应表是每个块的起始位置在列表的下标位置
  3. bei

---

哈希查找

• 原理：类似于java中hashmap实现原理