#pragma once
/*
--- 顺序查找 ---
按数组从头开始一一查找。
*/
int SequenceSearch(int nArray[], int nLength, int nValue)
{
for (int n = 0; n < nLength; ++n)
{
if (nArray[n] == nValue)
{
return n;
}
}
return -1;
}
/*
--- 折半查找 ---
1、确定数组的折半中点，对数组折半；
2、比较查找的数据a与中点数据b的大小关系，若a<b则对数组的后半部分重复步骤1，若a>b则对数组的前半部分重复步骤1，直到数组元素为1；
3、判断该元素是否为要找的元素。
*/
int HalfSearch(int nArray[], int nLow, int nHigh, int nValue)
{
int nIndex = -1;
if (nLow < nHigh)
{
int nMid = (nLow + nHigh) / 2;
if (nArray[nMid] > nValue)
{
nIndex = HalfSearch(nArray, 0, nMid - 1, nValue);
}
else if (nArray[nMid] < nValue)
{
nIndex = HalfSearch(nArray, nMid + 1, nHigh, nValue);
}
else if (nArray[nMid] == nValue)
{
nIndex = nMid;
}
}
return nIndex;
}
/*
--- 哈希查找 ---
1、确定哈希的key与value的关系，及冲突的解决方案；
2、将数据插入到哈希数组；
3、根据value结合冲突解决方案查找key。
*/
void InsertHash(int nArray[], int nValue, int nHashBase)
{
int nKey = nValue % nHashBase;
while(nArray[nKey] != 0)
{
nKey = (++nKey) % nHashBase;
}
nArray[nKey] = nValue;
}
int SearchHash(int nArray[], int nValue, int nHashBase)
{
int nKey = nValue % nHashBase;
while(nArray[nKey] != 0 && nArray[nKey] != nValue)
{
nKey = (++nKey) % nHashBase;
}
return (nArray[nKey] == nValue nKey : -1);
}
void Test_HashSearch()
{
int nArray = {0};
InsertHash(nArray, 2, 5);
InsertHash(nArray, 3, 5);
InsertHash(nArray, 7, 5);
InsertHash(nArray, 1, 5);
InsertHash(nArray, 4, 5);
int nKey = SearchHash(nArray, 2, 5);