文檔聲明：
以下資料均屬于本人在學(xué)習(xí)過(guò)程中產(chǎn)出的學(xué)習(xí)筆記封豪，如果錯(cuò)誤或者遺漏之處佛点，請(qǐng)多多指正。并且該文檔在后期會(huì)隨著學(xué)習(xí)的深入不斷補(bǔ)充完善挂洛。
資料僅供學(xué)習(xí)交流使用礼预。
作者：Aliven888
1、簡(jiǎn)述
? 程序設(shè)計(jì)的關(guān)鍵就是算法虏劲，算法簡(jiǎn)單來(lái)說(shuō)就是程序設(shè)計(jì)時(shí)問(wèn)題解題步驟或者數(shù)據(jù)數(shù)據(jù)的流程托酸。這里我們將介紹以下幾種常用的算法：迭代法、窮舉法柒巫、遞推法励堡、遞歸發(fā)、回溯法堡掏、貪婪法应结、查找算法、排序算法泉唁。
本章節(jié)主要介紹查找算法鹅龄。
2、查找算法
? 查找算法：這里我們介紹兩種比較常見(jiàn)的查找算法：順序查找和二分查找亭畜。
2.1扮休、順序查找
? 順序查找：一般用于在數(shù)組（或者鏈表）中查找指定的某個(gè)元素（或者節(jié)點(diǎn)）。要查找的數(shù)據(jù)一般稱(chēng)為關(guān)鍵字拴鸵，順序查找就是將給定的目標(biāo)值逐個(gè)與數(shù)組元素（或者鏈表節(jié)點(diǎn)）進(jìn)行比較玷坠，如果有與目標(biāo)值相同的數(shù)組元素（或者鏈表節(jié)點(diǎn)）蜗搔，則查找成功并輸出關(guān)鍵信息，否則認(rèn)為查找失敗侨糟，沒(méi)有與目標(biāo)值相同的元素（或者節(jié)點(diǎn)）碍扔。
特點(diǎn)：
? 適用于在無(wú)序的數(shù)據(jù)集合中查找目標(biāo)值。缺點(diǎn)就是在找到目標(biāo)值之前要把其他所有值遍歷一遍秕重。
代碼實(shí)例：
int onFindValuePos(int iList[], int iLen, int key)
{
int iRet = -1;
for (size_t i = 0; i < iLen; i++)
{
if (key == iList[i])
{
iRet = i;
break;
}
}
return iRet;
}
int main()
{
int iList[] = {1,2,3,4,5};
int iLen = 5;
int key = 3;
cout << "3 pos is [" << onFindValuePos(iList, iLen, key) << "]" << endl;
system("pause");
return 0;
}
運(yùn)行結(jié)果：
2.2不同、二分查找
? 二分查找：數(shù)據(jù)集合一般是有序的，如果不是有序的溶耘，在使用二分法之前需要先進(jìn)行排序二拐。
二分法思想：
- 把查找范圍對(duì)半分為兩部分。
- 比對(duì)目標(biāo)值與中間數(shù)據(jù)的大小凳兵，判斷該目標(biāo)值屬于前半部分還是后半部分百新。
- 對(duì)目標(biāo)值所屬的部分在分為兩部分，然后再將該目標(biāo)值與此時(shí)的中間值對(duì)比庐扫，找對(duì)當(dāng)前所屬的部分饭望，然后依次往復(fù)，直到遍歷完數(shù)據(jù)集合或者找到目標(biāo)值所在的位置（最后一個(gè)分割形庭，兩部分長(zhǎng)度都為1表示執(zhí)行完成）铅辞。
代碼實(shí)例：
int onFindValuePos(int iList[], int iLen, int key)
{
int iRet = -1;
int iFront = 0;
int iTail = iLen - 1;
int iMid = 0;
while (iFront <= iTail)
{
iMid = (iTail + iFront) / 2;
if (key == iList[iMid])
{
iRet = iMid;
break;
}
else if(key < iList[iMid])
{
iTail = iMid - 1;
}
else
{
iFront = iMid + 1;
}
}
return iRet;
}
int main()
{
int iList[] = {1,2,3,4,5,6,7,8,9};
int iLen = 9;
int key = 5;
cout << "5 pos is [" << onFindValuePos(iList, iLen, key) << "]" << endl;
system("pause");
return 0;
}
運(yùn)行結(jié)果：
