順序查找概念：從表的另一端開始，一次將記錄的關(guān)鍵字和給定值進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字和給定的值相等，則查找成功，反之則查找失敗。
ASL:平均查找長(zhǎng)度
pi查找概率，ci查找次數(shù)
eg：序列1，2，3
查找1的次數(shù)為1概率為1/3，2為兩次概率1/3，3的次數(shù)為3概率1/3?
將123的查找率*查找次數(shù)的結(jié)果累加得到?平均查找次數(shù)
?
順序查找的代碼實(shí)現(xiàn)：（這里我么用的順序表查找）?
//順序查找
typedef struct List
{
int* data;//數(shù)據(jù)元素
int* length;//數(shù)據(jù)長(zhǎng)度
int size;//有效數(shù)據(jù)個(gè)數(shù)
}List;
List* initList(int length)
{
List* list = (List*)malloc(sizeof(List));
list->length = length;
list->data = (int*)malloc(sizeof(int) * length);
list->size = 1;//size等于1的時(shí)候說明帶有哨兵，后面的數(shù)據(jù)從第二個(gè)位置開始存元素。
return list;
}
void listAdd(List* list,int data)
{
if (list->size == list->length)//所存儲(chǔ)的有效數(shù)據(jù)已經(jīng)等于空間大?。臻g已經(jīng)滿了）
{//這里我們重新定義一個(gè)newlength，防止開始length為0時(shí)，length*2=0；
int newlength = list->length == 0 ? 4 : list->length * 2;
int* tmp = (List*)realloc(list->data, newlength * sizeof(int));
if (tmp == NULL)
{
printf("空間開辟失敗\n");
exit(-1);
}
else
{
list->data[list->size] = data;
list->size++;
}
}
else
{
list->data[list->size] = data;
list->size++;
}
}
void printlist(List* list)
{
for ( int i = 0; i <list->size ; i++)
{
printf("%d ->", list->data[i]);
}
printf("NULL\n");
}
int search(List* list, int key)
{
int i=0;
list->data[0] = key;
//for循環(huán)后面沒有語句只有分號(hào)時(shí)，當(dāng)不滿足for循環(huán)的條件后循環(huán)結(jié)束不再進(jìn)行，直接進(jìn)行下一語句。
for (i = (list->size) - 1; list->data[i] != key; i--);//for循環(huán)后面沒有語句的執(zhí)行的時(shí)候需要添加分號(hào)，防止后面的語句直接進(jìn)入for循環(huán)中。
return i;//如果返回的為0則認(rèn)為沒有查找到，因?yàn)槲覀儼岩檎业脑胤旁诹祟^節(jié)點(diǎn)當(dāng)中。
}
int main()
{
List* list = initList(5);
listAdd(list, 1);
listAdd(list, 2);
listAdd(list, 3);
listAdd(list, 4);
listAdd(list, 5);
printlist(list);
printf("%d\n", search(list, 3));
return 0;
}順序查找的ASL：第一個(gè)節(jié)點(diǎn)需要1次，第n個(gè)節(jié)點(diǎn)則需要n次
則總該查找的次數(shù)為Sn=n*（n+1）/2（等差數(shù)列求和公式）
每次查找的概率為1/n
所以順序查找的ASL為：n*（n+1）/2*（1/n）=(n+1)/2?
所以時(shí)間復(fù)雜度為O（n）。
二分查找L(折半查找):
前提條件是有序序列，即每次從序列的中間開始于所要查找的元素比較，如果中間元素小于key（要查找的元素）則從中間元素的右邊查找（以中間元素+1為首元素，尾元素不變，再去求mid于key相比）。同理若key<mid則要從mid的左邊尋找（以中間元素-1為尾元素，首元素素不變，在去求mid于key比較），若key等于mid則返回。
代碼實(shí)現(xiàn)：利用循環(huán)查找
//循環(huán)查找
int binarysearch(int key,List* list)
{
int start = 0;
int end = list->size - 1;
int mid = 0;
while (start<=end)/如果我們的首元素下標(biāo)大于尾元素下標(biāo)則說明我們已經(jīng)遍歷完整個(gè)序列不存在要找的元素
{
mid = (start + end) / 2;
if (list->data[mid] < key)
{
start = mid + 1;
}
else if (list->data[mid]>key)
{
end = mid - 1;
}
else
{
return mid;
}
}
return -1;//-1表示不存在
}
遞歸實(shí)現(xiàn)二分查找：
//遞歸查找 1.分半2查找（左查/右查）。
int binarysearchRecursion(int key, List* list, int start, int end)
{
//出口
if (start == end)//每個(gè)遞歸都有一個(gè)終止條件相當(dāng)于我們while中的start<=end，當(dāng)兩個(gè)下標(biāo)相等時(shí)進(jìn)行判斷如果等于key則返回任意一個(gè)下標(biāo)，如果不相等則說明沒有找到
{
if (list->data[start]==key)
{
return start;
}
else
{
return -1;
}
}
int mid = (start + end) / 2;
//每次查找不到進(jìn)行遞歸，看key于mid的比較來判斷如果縮小范圍
if (list->data[mid] < key)
{
return binarysearchRecursion(key, list, mid+1, end);
}
else if (list->data[mid]>key)
{
return binarysearchRecursion(key, list, start, mid - 1);
}
else
{
return mid;
}
}?二分查找的時(shí)間復(fù)雜度：（兩個(gè)二分查找的世家復(fù)雜度相同所以我們只講解一個(gè)即可）
我們可以把線性表堪稱一顆樹（因?yàn)榫€性表是有序的比key小的都在其坐標(biāo)，比它大的都在其右邊）
eg：
?樹的查找：節(jié)點(diǎn)在第幾層需要查找?guī)状危琱層需要查找h次（所有的算法都符合此條件）
假設(shè)有n個(gè)節(jié)點(diǎn)，h層==》由樹的公式得到n=2^(h-1)? ?一棵滿二叉樹。
滿二叉樹：每一層有2^(h-1)個(gè)節(jié)點(diǎn)
每一層查找次數(shù)：節(jié)點(diǎn)個(gè)數(shù)*層數(shù)==2^(h-1)*h
每層的ASL：查找次數(shù) *概率=1/n*2^(h-1)*h
分解求2^(h-1)*h如何用n來代替
觀察得此為等差*等比數(shù)列，求法（錯(cuò)位相減Sn-hSn）
3，4式聯(lián)立：?
?
?
?文章來源地址http://www.zghlxwxcb.cn/news/detail-459403.html
再去×1/n得到整個(gè)順序的ASL?
?再利用我們數(shù)學(xué)極限n趨向足夠大的時(shí)候前面的分式可以約掉，所以結(jié)果
約等于：兩個(gè)都可
?文章來源：http://www.zghlxwxcb.cn/news/detail-459403.html
順序查找于二分查找以簡(jiǎn)略的講完，一些圖片資料與代碼都借鑒于b站upTyrantLucifer
?
?
?
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-查找（順序查找與二分查找的講解與代碼實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
