数据结构常见的三大查找
三种查找算法:顺序查找，二分法查找（折半查找），分块查找，散列表
顺序查找：
平均：(n+1)/2 最多（找不到）n+1
折半查找：
就是二分查找，前提是大小有序排列的顺序表
步骤：（1）确定查找区间的中点位置：mid=[(low+high)/2]，其中，low为起始位置， high为终止位置
（2）将位于mid位置处的数据元素的关键字与给定值key进行比较
1. key=elem[mid].key 成功
2. key<elem[mid].key 则high=mid -1
3. key>elem[mid].key 则low=mid-1
（3）重复，直到2查找成功或者low>high
#include <iostream>
using namespace std;
int bansearch(int *p, int key)
{
int low = 0,high = 7,mid=0;
while (key != p[mid])
{
mid = (low + high) / 2;
if (key > p[mid])low = mid + 1;
if (key < p[mid])high = mid - 1;
if (low > high)return 0;
}
return mid + 1;
}
int main()
{
int a[7] = { 1,3,9,4,5,10,2 };
int i, j, temp,k;
cin>>k;
//先排序 小--大
for (j = 0; j < 6; j++)
for (i = 0; i < 6; i++)
{
if (a[i] > a[i + 1]) {
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
for (i = 0; i < 7; i++)
{
cout << a[i] << " ";
}
i=bansearch(a, k);
cout << "成功，位置在： " << i;
system("Pause");
return 0;
}
分块查找（索引顺序查找）：
也叫索引顺序查找，算法实现除了需要查找表本身之外，还需要根据查找表建立一个索引表。例如图 1，给定一个查找表，其对应的索引表如图所示：
图 1 中，查找表中共 18 个查找关键字，将其平均分为 3 个子表，对每个子表建立一个索引，索引中包含中两部分内容：该子表部分中最大的关键字以及第一个关键字在总表中的位置，即该子表的起始位置。
建立的索引表要求按照关键字进行升序排序，查找表要么整体有序，要么分块有序。
分块有序指的是第二个子表中所有关键字都要大于第一个子表中的最大关键字，第三个子表的所有关键字都要大于第二个子表中的最大关键字，依次类推。
块（子表）中各关键字的具体顺序，根据各自可能会被查找到的概率而定。如果各关键字被查找到的概率是相等的，那么可以随机存放；否则可按照被查找概率进行降序排序，以提高算法运行效率。
例子代码：
#include<iostream>
using namespace std;
//索引表
typedef struct
{
int key;
int address;
}IdxTable;
typedef IdxTable indxtable[3];
//所有节点信息表
typedef struct
{
int key;
}NodeTable;
typedef NodeTable nodetable[18];
//二分查找
int IndxSearch_erfen(indxtable idx, int m, int key1)
{
int left = 0, right = m - 1, mid;while (left <= right)
{
mid = (left + right) / 2;
if (idx[mid].key >= key1 && idx[mid - 1].key < key1)
{
return idx[mid].address;
}
else if (idx[mid].key < key1)
left = mid + 1;
else if (idx[mid].key > key1)
right = mid - 1;
}
}
//顺序查找
int IndxSearch_shunxu(int n, int m, int key1, indxtable idx, nodetable r)
{
//int b=n/m//每块的个数
int b = n / m, i = IndxSearch_erfen(idx, m, key1);
int data_n = i + b;//数据表起始位置到某块终点的长度
while (i < data_n&&r[i].key != key1)
i++;
if (i >= data_n)
return -1;
else
return i;
}
int main()
{
nodetable r;
int k;
indxtable idx;
int a[] = { 22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53 }, i;
//数据表
printf("查找表(地址)： \n");
for (i = 0; i < 18; i++) {
r[i].key = a[i];
printf("%d(%d),",a[i],i);
}
printf("\n");
printf("请输入要查找的关键字：\n");
scanf("%d",&k);
//索引表
idx[0].key = 22; idx[0].address = 0;
idx[1].key = 48; idx[1].address = 6;
idx[2].key = 86; idx[2].address = 12;
//查找结果
if ((i = IndxSearch_shunxu(18, 3, k, idx, r)) != -1)
printf("关键字%d的位置是%d\n", k, i);
else
printf("关键字%d不在表中", k);
system("Pause");
return 0;
}
运行：