查找算法

顺序查找(Sequential Search)

说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表

复杂度：O(n)

基本思想：顺序查找也称线性查找(Liner Search)，属于无序查找算法。

从数据结构线性表的一端开始，顺序扫描，依次比较扫描到的结点，若相等则表示查找成功；

若扫描结束仍没有找到目标，则查找失败；

查找失败则需要进行n+1次比较，则时间复杂度为 O(n)

C++实现

  • Code Example 1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    #include "stdafx.h"
    #include <iostream>

    template<typename T,typename V> int sequential_search(const T *arr, V key, size_t len)
    {
    	for (int i = 0; i < len; i++)
    	{
    		if (key == arr[i])
    			return i;
    	}
    	return -1;
    }

    int main(int argc, char** argv)
    {
    	int arr1[] = { 1,1,2,3,5,8,13 };
    	int len1 = (int)sizeof(arr1) / sizeof(*arr1);
    	int key1 = 8;
    	std::cout << "Index: " << sequential_search(arr1, key1, len1) << std::endl;

    	char arr2[] = { 'a','b','c','d','e','f','g' };
    	int len2 = (int)sizeof(arr2) / sizeof(*arr2);
    	char key2 = 'e';
    	std::cout << "Index: " << sequential_search(arr2, key2, len2) << std::endl;

    	system("pause");
    	return 0;
    }
  • Code Example 2
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int main(int argc, char** argv)
    {
    	int arr[] = { 1,1,2,3,5,8,13 };
    	int count = 0;
    	int key = 13;
    	for (auto elem : arr)
    	{
    		if (key == elem)
    		{
    			system("pause");
    			return 0;
    		}
    		count++;
    	}
    	std::cout << "not fund !" << std::endl;
    	system("pause");
    	return -1;
    	
    }

二分查找(Binary Search)

说明：元素必须是有序的，若无序则需先排序

复杂度：O(log2n)

基本思想：将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；

如果x<a[n/2],则只要在数组a的左半部分继续搜索x

如果x>a[n/2],则只要在数组a的右半部搜索x.

时间复杂度无非就是while循环的次数,总共有n个元素，

渐渐跟下去就是n,n/2,n/4,….n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数

由于你n/2^k取整后>=1，即令n/2^k=1

可得k=log2n,（是以2为底，n的对数）

所以时间复杂度可以表示O(h)=O(log2n)

C++实现

  • 随机数生成
1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdlib>
#include<ctime>

srand((unsigned)time(NULL));
std::cout<<rand()<<std::endl;

取得(0,x)的随机整数：rand()%x；
取得(a,b)的随机整数：rand()%(b-a)；
取得[a,b)的随机整数：rand()%(b-a)+a；
取得[a,b]的随机整数：rand()%(b-a+1)+a；
取得(a,b]的随机整数：rand()%(b-a)+a+1；
取得0-1之间的浮点数：rand()/double(RAND_MAX)
  • 每次都从中间分，完成查找次数相对稳定
1
int mid = (left + right) / 2;
  • 每次的mid值由左右界限来生成随机值
1
int mid = rand() % (right - left + 1) + left;
  • Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <math.h>
#include <cstdlib>
#include <ctime>

template<typename T,typename V> int binary_search(V *arr,T key, size_t len)
{
	int left = 0;
	int right = len - 1;
	int count = 0;
	srand((unsigned)time(NULL));
	while (left <= right)
	{
		//int mid = (left + right) / 2;
		int mid = rand() % (right - left + 1) + left;
		if (arr[mid] == key)
		{
			std::cout << "real times to target:" << "\t\t" << count << std::endl;
			return mid;
		}
		else if(key > arr[mid])
			left = mid + 1;
		else
			right = mid - 1;
		
		count++;
	}
	return -1;
}

int main(int argc, char** argv )
{
	char key = 'a'+ 29;
	const int len = 30;
	char arr[len];
	for (int i = 0; i < len; i++)
		arr[i] = 'a' + i;

	std::cout << "expected times to target:" << "\t" << log2(len) << std::endl;
	std::cout << binary_search(arr, key, len) << std::endl;

	system("pause");
	return 0;
}

插值查找(Interpolation Search)

在二分查找的基础上，二分查找是每次都分一办查找。但是我们查字典的时候并不会是一半一半的翻页。

比如查c开头的单词，我们会从字典的**(c-a)/(z-a)**部分打开。

这种折半的查找方式并不是每次折半1/2，因此我们将二分法的折1/2的方式优化为自适应的**(c-a)/(z-a)**的比例。

二分法：mid=(left+right )/2, 即mid=left+1/2(right -left);*

插值法则是： mid = left+ (key - arr[left])/(arr[right] - key) * (right - left)

基本思想：基于二分法，改进查找点的自适应性，从而提高效率。插值查找也属于有序查找。

复杂度：查找成功/失败都是$O(log_2(log_2^n))$。

注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

C++实现

  • Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    #include "stdafx.h"
    #include <iostream>
    #include <math.h>

    template<typename T, typename V> size_t interpolation_search(V *arr, T key, size_t len, size_t &count)
    {
    	int left = 0;
    	int right = len - 1;
    	int mid = 0;

    	while ((arr[left]!=arr[right]) && (key>arr[left]) && (key<arr[right]))
    	{
    		count++;
    		mid = left + (right - left) * (key - arr[left]) / (arr[right] - arr[left]);
    		if (key > arr[mid])
    			left = mid + 1;
    		else
    			right = mid - 1;
    	}
    	if (arr[mid] == key)
    		return mid;
    	else
    		return -1;
    }

    int main(int argc, char** argv)
    {
    	char key = 'a' + 10;
    	const size_t len = 29;
    	size_t count = 0;
    	char arr[len];
    	for (int i = 0; i < len; i++)
    		arr[i] = 'a' + i;

    	std::cout << "expected times to target:\t" << log2(log2(len)) << std::endl;
    	std::cout << "position: \t" << interpolation_search(arr, key, len, count) << std::endl;
    	std::cout << "real times to target:\t" << count << std::endl;

    	system("pause");
    	return 0;
    }

**输出： **

1
2
3
expected times to target:       2.28036
position:       				10
real times to target:   		1

分块查找(Block Search)

分块有序：整个表中的元素未必有序，但若划分为若干块后，每一块中的所有元素均小于（或大于）其后面块中的所有元素。

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。首先须要对数组进行分块，分块查找须要建立一个“索引表”。索引表分为m块，每块含有N/m个元素，块内是无序的，块间是有序的，比如块2中最大元素小于块3中最小元素。先用二分查找索引表。确定须要查找的keyword在哪一块，然后再在对应的块内用顺序查找。

操作步骤：

　　step1 先选取各块中的最大关键字构成一个索引表；

　　step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

时间复杂度：O(log(m)+N/m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include "stdafx.h"
#include <iostream>

//索引表--结构体模板
template<typename T> struct Index_table
{
	T key;
	int link;
};

// index_able为索引表,x为原数组,N为数组大小，m为块大小, keyword为查找目标
template<typename T>  int index_order_search(Index_table<T> *index_able, T *x, int N, int m, T keyword)
{
	int L = (N + m - 1) / m;
	int i = 0;
	while (i < L && index_able[i].key < keyword)
		i++;
	if (i == L)
		return -1;
	else
	{
		for (int j = index_able[i].link; j < index_able[i].link + m; j++)
			if (x[j] == keyword)
				return j;
	}
	return -1;
}

int main(int argc, char** argv)
{
	//block1(22,0)    |block2(48,6)      |block3(86,12)
	//22,12,13,8,9,20,|33,42,44,38,24,48,|60,58,74,49,86,53
	//0 ,1 ,2 ,3,4,5 ,|6 ,7 ,8 ,9 ,10,11,|12,13,14,15,16,17
	int arr[] = {22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53};
	int len = (unsigned)sizeof(arr) / sizeof(*arr);
	int block_size = 6;
	int target = 33;

	Index_table<int> index_table[3];
	index_table[0].key = 22;
	index_table[0].link = 0;
	index_table[1].key = 48;
	index_table[1].link = 6; 
	index_table[2].key = 86;
	index_table[2].link = 12;

	std::cout << index_order_search(index_table, arr, len, block_size, target) << std::endl;

	system("pause");
	return 0;
}
Algorithm
Cpp Algorithm

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！