查找算法总结——面试(一)

====================

顺序查找算法

====================

1. 算法描述

  顺序比较即可。

2. 平均查找长度

  (n+1)/2, 其中n为表长。

3. 算法实现

    省略

4. 优化思想

  根据经验，目前被查到越多的元素，将来可能被查到的可能性也越大。所以可以考虑，每次查找到一个元素后，将它和直接前驱交换位置。

如果上述的经验从概率上来讲是成立的，则可以加快顺序查找的速度。

====================

二分查找算法

====================

1. 算法描述

  限制：待查表必须是有序的向量(在内存中连续存储)

  首先和数组中点比较，如果等于则返回，如果小于中点则在左边区间查找，如果大于中点则在右边区间查找。

2. 平均查找长度

  lg(n+1)

3. 算法实现

(1) 非递归方式

static const int ERROR = -1; 

template<typename T>

int binary_search(T *array, const int size, const T & key)

{

 if(NULL == array || size < 1)

 {

  cout << "illegal input!" << endl;

  return ERROR;

 }

 int low = 0, high = size - 1;

 int mid_index = 0;

 while(low <= high)

 {

  mid_index = (low+high)/2;

  if(key == array[mid_index])

  {

   return mid_index;

  }  

  else if(key > array[mid_index])

  {

   low = mid_index + 1; 

  }

  else 

  {

   high = mid_index - 1;

  }

 }

 return ERROR;

}

(2) 递归方式

template<typename T>

int binary_search_iter(T *array, const int low, const int high, const T & key)

{

 if(low > high)

 {

  return -1;

 }

 int mid_index = (low+high)/2;

 if(key == array[mid_index])

 {

  return mid_index;

 }

 else if(key > array[mid_index])

 {

  return binary_search_iter(array, mid_index+1, high, key);

 }

 else 

 {

  return binary_search_iter(array,low, mid_index-1, key);

 }

}

====================

分块查找算法

====================

1. 基本思想

    以增加空间复杂度为代价(存储每块中的最大值已经最大值的位置)，为原数组做一个索引(索引本身是递增有序的)，这样先查索引，再查块内位置。如果索引的选择科学有效，则可以获得比顺序查找快的速度。

2. 算法描述

   抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即: ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。

   先用二分法查到元素可能所在的块起始位置，而后在块内进行顺序查找。

3. 平均查找长度

   平均查找长度在顺序查找和二分查找之间，并且当结点数为元素数量的平方根时，查找长度最小。

=======================

二叉排序树上的查找

=======================

1.2 动态查找表 （1）二叉排序树 性质：若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值，若它的柚子树不空，则右子树上的所有节点的值均大于或等于它的根节点的值，左右子树本身又各是一棵二叉排序树，中序遍历二叉排序树可得到一个关键字的有序序列。 数据结构： typedef struct{ KeyType key;

}ElemType; typedef struct BiNode{ ElemType data; struct BiNode *lchild,*rchild; }BiTNode,*BiTree; 查找过程：在二叉排序树中查找是否存在关键字为key的数据元素，若存在返回其地址，否则返回NULL 若二叉排序树为空，则查找不成功，若key等于根节点的关键字，则查找成功，若key小于根节点的关键字，继续在左子树上查找，若大于根节点关键字，则在右子树上查找。拥有类似折半查找的特性，又采用了链表作为存储结构。 BiTree SearchBST(BiTree T,KeyType k){ if(!T){ if(T->data.key==k) return T; else if(T->data.key<k) return(SearchBST(T->lchild,k)); else return(SearchBST(T->rchild,k)); } else  return NULL; }

=======================

1.3 哈希 =========================== 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系，这样，不经过比较，一次就能得出所查元素是否存在。 哈希函数构造方法：直接定址法、数字分析法、平方取中法、折叠法、除数求留法。 处理冲突的方法： （1）开放定址法，当冲突发生时，形成一个探测序列，沿此序列逐个地址探查，知道找到一个空位置，将发生冲突的记录放到该地址中，Hi=(H(key)+di)MOD m di是增量序列，分为线性探测再散列，二次探测再散列，伪随机探测再散列 （2）再哈希法，构造若干个哈希函数，当冲突发生时，使用另外一个哈希函数计算哈希地址 （3）链地址法，将所有的关键字为同义词的记录存储在一个单链表中，并用一个一维数组存放单链表的头指针