查找概论1

打算复习查找这一章，做点笔记吧

基本概念

---

• 查找表：同一类型数据元素构成的集合，其中数据元素中的某个数据项根据唯一性可以分为关键字和次关键字等
• 查找简单分为：静态查找（只进行查找操作，适合线性表结构，二分查找）和动态查找（查找时可以插入数据元素也可以删除数据元素，二叉排序树等）

顺序表查找

---

• 顺序表查找即从头开始逐个比较,复杂度O(n)

int sequential_search（int *a, int n, int key）
{
     for(int i = 0;i<n;i++)
     {if(a[i]==key) return i;}
     return -1;
}
//上述代码可以进行一定的优化
int sequential_search（int *a, int n, int key）
{
     if(a[0] == key) return 0;
     int temp = a[0];
     a[0] = key;
     int i = n-1;
     while(a[i--]!=key);
     a[0] = temp;
     return i;
}

有序表查找

---

• 折半查找\二分查找\binary search。基于有序表，每次取中间值比较。复杂度O(logn)

int binary_search(int *a,int n,int key)
{
     int low = 0,high = n-1,mid;
     while(low<=high)
     {
          mid = (high + low)/2;
          if(key < a[mid])
               high = mid-1;
          else if (key > a[mid])
               low = mid + 1;
          else
               return mid;
     }
     return -1;
}

• 为什么一定需要折半查找呢？是否可以1/4查找，引入插值查找。复杂度O(logn)

mid = low + (high-low)*(key - a[low])/(a[high]-a[low]);

• 斐波那契查找复杂度O(logn)，前面是插值查找是指当数据分布较为均匀情况下能够提高性能。但当查找值在数据在右侧的时候，斐波那契查找具有较高的性能，如下图所示。其查找核心是

1\当key=a[mid]时，查找成功;
2\当key>a[mid]时，新的查找范围是第mid+1个到第high个，范围个数为F[k-2] - 1个
3\当key<a[mid]时，新的查找范围是第low个到第mid-1个，范围个数为F[k-1] - 1个

QQ截图20140807215512.jpg

• 小结：三种有序表的查找的本质在于分割点的选择不同。

线性索引查找

---

• 实际很多过程，要使数据有序是很困难的，因此许多数据都是按照先后顺序进行存储。对于这样的数据加快查找方法就是采用索引
• 索引就是把关键字与对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项包括关键字和对应的记录在存储器中的位置。
• 索引按照结构划分线性索引、树形索引、和多级索引，其中线性索引指索引项组织为线性结构，包括:

稠密索引——每一个记录对应一个索引项，索引项按照关键码有序排序
分块索引——每块对应一个索引项，块内无序，块间有序
倒排索引——根据属性值、次关键码选择记录编号的过程

reference

---

• 大话数据结构