搜索

查找

若给出的序列是线性的，我们就可以用查找来做，如果是有序的则使用二分查找，如果是无序的即可用暴力的顺序搜索也可以通过构造二叉搜索树来查找。

在无序记录集Ro,R1,...,Rn-1中搜索关键词为key的记录R：在记录集中的位置i(0≤i≤n-1)。

它的查找过程是：从第一个记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个记录，其关键字和给定值比较都不等时，则没有所查的记录，查找不成功。

例子：53 78 65 17 87 9 81 45 23 67
搜索：90 45

从左到右遍历，90 —> nofind， 45 —> 7

二叉搜索树（Binary Search Tree,BST)

二叉搜索树又称二叉排序树。它或者是一颗空树，或者是具有下列性质的二叉树。

  • 若它的左子树不空，则左子树所有结点的值均小于它的根结构的值。
  • 若它的右子树不空，则右子树所有结点的值均大于它的根结构的值。
  • 它的左右子树也分别为二叉搜索树。
  • 没有键值相等的结点。

例子：53 78 65 17 87 9 81 45 23 67
搜索：90 45

1
2
3
4
5
6
7
8
>> 中序遍历(左根右)
            53
			/\
		  17  78
		 /\	  /\
	    9 45 65 87
		  /  \   /
		23   67 81

在有序记录集中，每次把待查区间中间位置记R_mid的关键词与key比较，若不等则缩小搜索区间并在新的区间内重复上述过程，直到搜索成功或者搜索区间长度为0(搜索不成功）为止。

例子：12 23 26 37 54 60 68 75 82 96

搜索：96 24

1
2
3
4
1.l = 0, r = 10 - 1, mid = 4, nums[mid] < 96
2.l = mid + 1 = 5, r = 10 - 1. mid = 5 + (9 - 5)/2, nums[mid]<96
3.l = mid + 1 = 8, r = 9, mid = 8 + (9 - 8)/2, nums[mid]<96
4.l = mid + 1 = 9, r = 9, mid = 9, nums[mid] = 96, return 9

遍历

对于非线性序列，搜索通过遍历进行。

深度优先搜索

假设G = (V,E）以S为起点（源点）进行搜索。

首先标识S为已访问结点，接着寻找与S相邻的结点ω，若ω是未被访问结点，则以ω为起点进行深度优先搜索，若ω是已被访问结点，则寻找其它与S相邻的结点，直到与S有路径相通的所有结点都被访问过。

左边是图，右边是图的存储结构，用邻接表来存储；

邻接表左边是存储图的顶点，右边是边表，存与顶点所构成的边。

广度优先搜索

假设G = (V,E）以S为起点（源点）进行搜索。首先标识S为已访问结点，接着问S的邻接点ω1,ω2,...,ωt然后问ω1,ω2,...,ωt的未被问的邻接点，以此类推，直到与S有路径相连的所有结点都被访问到。

先来先服务的思想，类似队列。

广度优先搜索序列：V0, V1, V2, V3, V4, V5, V6, V7