【算法】查找算法
查找算法
查找的定义
查找:又称检索或查询，是指在查找表中找出满足一定条件的结点或记录对应的操作。
查找表:在计算机中，是指被查找的数据对象是由同一个类型的记录构成的集合，如顺序表、链表、二叉树和哈希表等。
查找效率:查找算法中的基本运算是通过记录的关键字与给定值进行比较，所以查找的效率通常取决于比较所花的时间，而时间取决于比较的次数。通常以关键字与给定值进行比较的记录个数的平均值来计算。
查找操作及分类
操作：
- 查找某个“特定的”数据元素是否成存在在查找表里。
- 某个“特定的”数据元素的各种属性。
- 在查找表中插入一个数据元素。
- 从查找表中删除某个数据元素。
分类:
若对查找表只进行(1)或(2)两种操作，则称此类查找表为静态查找表。 若在查找的过程中同时插入查找表中存在的数据元素，或者从查找表中删除已经存在的某个数据元素，则称次类查找表为动态查找表。
数组和索引
索引把线性表分为若干块，每一块中的元素存储顺序是任意的，但是块与块之间必须按关键字大小顺序排列。即前一块中的最大关键字值小于后一块中的最小关键字值。
分块以后，为了快速定义块，还需要建立一个索引表，索引表中的一项对应于线性表中的块，索引项由键域和链域组成。键域存放相应关键字的键值，链域存放指向本块第一个节点和最后一个节点的指针，索引表按关键字由小到大的顺序排列！
数组是特殊的块索引（一个块一个元素）：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xDbRyWBM-1635489015712)(查找算法.assets/image-20211028180054162.png)]
哈希表是非常经典的块索引! [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6LawbrgF-1635489015715)(查找算法.assets/image-20211028180620292.png)]
分块查找的算法分两步进行，首先确定所查找的节点属于哪一块，即在索引表中查找其所在的块，然后在块内查找待查询的数据。由于索引表是递增有序的，可采用二分查找，而块内元素是无序的，只能采用顺序查找。（块内元素较少，则不会对执行速度有太大的影响）
二分查找
二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。再重 复根据中间数确定目标范围并递归实行对半分割，直到中间数等于待查找的值或是目标数不在搜 索范围之内！
代码实现
#include<iostream>
using namespace std;
int BinarySearch(int* sorted, int len, int search)
{
int left = 0;
int right = 0;
int middle = 0;
left = 0;
right = len - 1;
while (left <= right)
{
middle = (left + right) / 2;
if (sorted[middle] == search)
{
return middle;
}
else if (sorted[middle] > search)
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}
return -1;
}
int main(void)
{
int arr[] = { 1,3,5,16,58,74,169 };
int search = 3;
int index = BinarySearch(arr, sizeof(arr) / sizeof(arr[0]),search);
cout << index;
return 0;
}如果要实现其他类型的比较查找
注意用void*类型接收不同类型，根据传进来类型的不同调用对应的比较函数。
代码实现
#include<iostream>
using namespace std;
int int_compare(const void* key1, const void* key2)
{
const int* ch1 = (const int*)key1;
const int* ch2 = (const int*)key2;
return *ch1 - *ch2;
}
int char_compare(const void* key1, const void* key2)
{
const char* ch1 = (const char*)key1;
const char* ch2 = (const char*)key2;
return *ch1 - *ch2;
}
int BinarySearch(void* sorted, int len,int elemSize,void *search, int(*compare)(const void* key1, const void* key2))
{
int left = 0;
int right = 0;
int middle = 0;
left = 0;
right = len - 1;
while (left <= right)
{
int ret = 0;
middle = (left + right) / 2;
ret = compare( (char*)sorted+(middle * elemSize),search);
if (ret == 0)
{
return middle;
}
else if (ret > 0)
{
right = middle - 1;
}
else
{
left = middle + 1;
}
}
return -1;
}
int main(void)
{
int arr[] = { 1,3,5,16,58,74,169 };
int search = 3;
int index = BinarySearch(arr, sizeof(arr) / sizeof(arr[0]),sizeof(int),&search,int_compare);
cout << index;
return 0;
}补充:上面代码中为什么要转成char类型指针
ret = compare( (char*)sorted+(middle * elemSize),search);什么类型的指针，增加偏移量的大小的是不同的。
例如：
char*指针 +1，内存偏移1字节
int* 指针 +1，内存偏移4字节因为我们的运算加的是对应数组元素类型的大小*middle,求出偏移的字节个数，所以转成char类型指针，可以保证我们加了几个这个类型的大小等同于与数组第一个元素相距了几个元素，得到对应的地址。
指针的运算！！！
如下图所示，+1和+4，指向的是同一个地址。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fLQp4abR-1635489015717)(查找算法.assets/image-20211028203724495.png)]
穷举搜索
有 20 枚硬币，可能包括 4 种类型：1 元、5 角、1 角和 5 分。 已知 20 枚硬币的总价值为 10 元，求各种硬币的数量。 例如：4、11、5、0 就是一种方案。而 8、2、10、 0 是另一个可能的方案，显然方案并不是 唯一的，请编写程序求出类似这样的不同的方案一共有多少种？ （1）编程思路。 直接对四种类型的硬币的个数进行穷举。其中，1 元最多 10 枚、5 角最多 20 枚、1 角最多 20 枚、5 分最多 20 枚。 如果以元为单位，则 5 角、1 角、5 分会化成浮点型数据，容易计算出错。可以将 1 元、5 角、1 角、5 分变成 100 分、50 分、10 分和 5 分，从而全部采用整型数据处理。
代码实现:
#include<iostream>
using namespace std;
int main(void)
{
int a100 = 0;//一元硬币的数量
int a50 = 0;
int a10 = 0;
int a5 = 0;
int count = 0;//可行方案总数
//for循环可以进行优化，根据上一个纸币面额所花费钱的多少
for (a100 = 0; a100 <= 10; a100++)
{
for (a50 = 0; a50 <= 20; a50++)
{
for (a10 = 0; a10 <= 20; a10++)
{
for (a5 = 0; a5 <= 20; a5++)
{
if (a100 * 100 + a50 * 50 + a10 * 10 + a5 * 5 == 1000 && (a100 + a50 + a10 + a5 == 20))
{
cout << "a100:" << a100 << " " << "a50:" << a50 << " " << "a10:" << a10 << " " << "a5:" << a5 << endl;
count++;
}
}
}
}
}
cout << "一共有" << count << "种可行方案" << endl;
return 0;
}穷举法(枚举法)的基本思想是:列出所有的可能情况，逐个判断有哪些是符合问题所要求 的条件，从而得到问题的全部解答。
它利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案。
用穷举法解决问题,通常可以从两个方面进行分析:
（1）问题所涉及的情况：问题所涉及的情况有哪些，情况的种数必须可以确定。把它描述出来。应用穷举时对问题所涉及的有限种情形必须一一列举，既不能重复，也不能遗漏。重复列 举直接引发增解，影响解的准确性；而列举的遗漏可能导致问题解的遗漏。 （2）答案需要满足的条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。把这些条件描述出来。
并行搜索
并发的基本概念： 所谓并发就是在同一实体上的多个事件同时发生。并发编程是指在同一台计算机上"同时"处理多个任务。
进程：
通常每个进程对应一个在运行中的执行程序，比如，QQ 和微信运行的时候，他们分别是不同的进程。
任一时刻，单个 CPU 一次只能运行一个进程，此时其他进程处于非运行状态。
线程：
一个进程可以拥有多个线程，每个线程可以可以独立并行执行，多个线程共享同一进程的资源，受进程管理。
要从一个无序数据集中进行搜索，我们可以将数据分成N个块，每块由一个线程来并行搜索。
代码实现
#include<iostream>
#include<time.h>
#include<stdio.h>
#include<windows.h>
using namespace std;
#define TEST_SIZE (1024*1024*200)
#define NUMBER 20
typedef struct _search
{
int* data;//搜索的数据集
size_t start;//搜索的开始位置
size_t end;//搜索的结束位置
size_t count;//搜索结果
}search;
DWORD WINAPI ThreadProc(void* lpParm)
{
search* s = (search*)lpParm;
time_t start, end;
cout << "新的线程开始执行..." << endl;
time(&start);
for (int j = 0;j <10;j++)
{
for (size_t i = s->start; i <= s->end; i++)
{
if (s->data[i] == NUMBER)
{
s->count++;
}
}
}
time(&end);
cout << "进程所用时间:" << end - start << endl;
return 0;
}
int main(void)
{
int* data = NULL;
int count = 0;
int mid = 0;
search s1, s2;
data = new int[TEST_SIZE];
for (int i = 0; i <TEST_SIZE; i++)
{
data[i] = i;
}
mid = TEST_SIZE / 2;
s1.data = data;
s1.start = 0;
s1.end = mid;
s1.count = 0;
s2.data = data;
s2.start = mid + 1;
s2.end = TEST_SIZE - 1;
s2.count = 0;
DWORD threadID1;//线程1的身份证
HANDLE hthread1;//线程1的句柄
DWORD threadID2;//线程2的身份证
HANDLE hthread2;//线程2的句柄
//创建线程
hthread1 = CreateThread(NULL, 0, ThreadProc, &s1, 0, &threadID1);
hthread2 = CreateThread(NULL, 0, ThreadProc, &s2, 0, &threadID2);
WaitForSingleObject(hthread1, INFINITE);
WaitForSingleObject(hthread2, INFINITE);
cout << s1.count + s2.count << endl;
return 0;
}腾讯云开发者
