二分查找
定義
對(duì)已經(jīng)排好序的數(shù)組進(jìn)行查找
對(duì)數(shù)組進(jìn)行操作
在查找失敗最多次數(shù)(向下取整加一)
二分查找的時(shí)間復(fù)雜度:
由于簡書不可以讀取latex公式鞋拟，這里推薦到我的主頁去看演闭。請點(diǎn)擊!
二分查找的代碼
int BinaryChop(int Num[],int nCount,int nValue)
{
int max_index = nCount-1;
int min_index = 0;
int Mid = 0;
while (min_index<=max_index)
{
Mid = (max_index+min_index)/2;
if(Num[Mid] == nValue)
return Mid;
if(Num[Mid]>nValue)
{
max_index = Mid-1;
}else
{
min_index = Mid+1;
}
}
return -1;
}
HashChop（哈希查找）
定義：對(duì)已經(jīng)建好散列表的數(shù)據(jù)進(jìn)行查找汹买。
哈希是查找速度最快的算法竖般。
缺點(diǎn):空間消耗非常大飒赃。
步驟
- 分析數(shù)據(jù)并定散列函數(shù)蜜托。
- 決定哈希沖突的解決辦法。
- 根據(jù)散列函數(shù)建散列表微酬。
- 對(duì)已經(jīng)建好的散列表進(jìn)行查找绘趋。
對(duì)于以上步驟第一步到第三步是建立散列表的過程。
散列函數(shù)
我們一般用求整取余法得封。
- 首先我們選取一個(gè)數(shù)M埋心，這個(gè)數(shù)最好是質(zhì)數(shù)（非硬性要求），但一定比數(shù)據(jù)元素個(gè)數(shù)小忙上，因?yàn)樵谕瑫r(shí)間復(fù)雜度下占用空間最小為宜拷呆，后面會(huì)提及。
- 當(dāng)M數(shù)確定下來后疫粥，我們定桶茬斧，桶為數(shù)據(jù)元素除以質(zhì)數(shù)M的各個(gè)余數(shù)徐鹤，也就是從0到M-1鸯旁，元素除以質(zhì)數(shù)M得桶所代表的余數(shù)达布，我們就把這個(gè)數(shù)據(jù)元素放入桶內(nèi)瘩燥，而且每個(gè)桶里只能放一個(gè)元素。
- 而當(dāng)數(shù)據(jù)元素除以質(zhì)數(shù)M得余數(shù)相同時(shí)眯搭，由于桶內(nèi)只能放一個(gè)元素虑粥，所以當(dāng)出現(xiàn)余數(shù)相同的元素時(shí)而不能放入桶內(nèi)時(shí)很洋，就產(chǎn)生了哈希沖突底哗。當(dāng)我們解決完哈希沖突后岁诉，也就建完散列表，就可以查找了跋选！
解決哈希沖突
- 開放地址法
- 線性探測法：在沖突位置順次后延一位放入桶內(nèi)涕癣。也就是說同為余數(shù)4的話，后來的數(shù)據(jù)就放入余數(shù)5的桶里前标。
- 線性補(bǔ)償法：首先定一個(gè)步長坠韩，遇到?jīng)_突時(shí)，按步長順次后延步長的長度放入桶內(nèi)炼列。
- 隨機(jī)探測法：找個(gè)隨機(jī)數(shù)來當(dāng)步長只搁，解決沖突如上個(gè)辦法。
- 拉鏈法：
- 在每個(gè)桶內(nèi)建立一個(gè)頭添加的鏈表俭尖，每個(gè)桶內(nèi)裝的是相應(yīng)鏈表的頭指針氢惋，將后來的元素依次頭添加在鏈表上。
舉例圖示
例如數(shù)組｛19，27明肮，55，41缭付，82柿估，89，16陷猫，9秫舌，22，98绣檬，104足陨，1，2娇未，205墨缘，46｝
HashChop
代碼
typedef struct node
{
int nValue;
int nIndex;
struct node *pNext;
}MyHash;
#define M 7
MyHash **CreateHashTable(int arr[],int nLength)
{
MyHash **pHash = NULL;
MyHash *pTemp = NULL;
int i;
int nIndex;
//申請哈希表表頭
pHash = (MyHash**)malloc(sizeof(MyHash*) * M);
memset(pHash,NULL,sizeof(MyHash*) * M);
//拉鏈法
for(i = 0;i<nLength;i++)
{
nIndex = arr[i]%M;
pTemp = (MyHash*)malloc(sizeof(MyHash));
pTemp->nIndex = i;
pTemp->nValue = arr[i];
//頭添加
pTemp->pNext = pHash[nIndex];
pHash[nIndex] = pTemp;
}
return pHash;
}
int HashChop(int arr[],int nLength,int nNum)
{
MyHash **pHash = NULL;
int nIndex;
MyHash *pMark = NULL;
if(arr == NULL || nLength <=0)
abort();
//建哈希表
pHash = CreateHashTable(arr,nLength);
//查詢
nIndex = nNum%M;
pMark = pHash[nIndex];
//遍歷鏈表
while(pMark)
{
if(pMark->nValue == nNum)
{
return pMark->nIndex;
}
else
{
pMark = pMark->pNext;
}
}
return -1;
}
