大學(xué)計(jì)算機(jī)基礎(chǔ) 課件 10.4.2二分查找

大學(xué)計(jì)算機(jī)基礎(chǔ)——基于計(jì)算思維（Windows10+Office2016）第10章算法思維與運(yùn)用10.4.2二分查找10.4查找算法問(wèn)題5二分查找某體校要招各類體育專長(zhǎng)人員，根據(jù)專業(yè)不同，對(duì)身高有不同的要求。現(xiàn)有若干人的身高數(shù)據(jù)按從低到高的順序存放在數(shù)據(jù)文件“data2.txt”中（每行一個(gè)），當(dāng)招生人員從鍵盤輸入一個(gè)身高值，請(qǐng)?jiān)谖募胁檎以撋砀咧?，若找到則給出其位置（第幾行），若沒(méi)找到，提示“nofound”。data2.txt若找到則給出其位置（第幾行）輸入查找若沒(méi)找到，提示“nofound”輸出問(wèn)題5二分查找1．問(wèn)題分析本問(wèn)題中數(shù)據(jù)集中的數(shù)據(jù)是有序的，已按從低到高的順序排好，那能不能利用這一條件提高查找效率呢？問(wèn)題5二分查找1．問(wèn)題分析先看這樣一個(gè)游戲：猜某件商品的價(jià)格，已知商品的價(jià)格范圍（假設(shè)為1~100元），每猜一次主持人可以回答游戲者所猜價(jià)格比實(shí)際價(jià)格高了還是低了，若在規(guī)定次數(shù)內(nèi)就能猜對(duì)者，就可免費(fèi)獲得該商品。為了減少猜的次數(shù)，提高命中的效率，你會(huì)怎樣猜呢？通常會(huì)從1到100元的中間值50元開(kāi)始猜，如果高了，則進(jìn)一步從1到50元的中間值25再開(kāi)始猜；而如果低了，則從50到100元的中間值75開(kāi)始猜，這種猜價(jià)格的方法稱為折半方法。把折半方法應(yīng)用在查找中，就稱為折半查找法（又稱二分查找），它是在一個(gè)有序的元素列表中查找特定值的一種方法，該順序可以是升序，也可以是降序。問(wèn)題5二分查找1．問(wèn)題分析二分查找順序查找問(wèn)題5二分查找2.算法實(shí)現(xiàn)設(shè)計(jì)折半查找子程序halfsearchhalfsearch的參數(shù)和順序查找算法中search的一樣，輸入?yún)?shù)有a、n、key，輸出參數(shù)有flag、wz。問(wèn)題5二分查找2.算法實(shí)現(xiàn)設(shè)計(jì)折半查找子程序halfsearch假設(shè)用left表示每次查找范圍的最小值，right表示每次查找范圍的最大值，第1次查找范圍是(left=1,right=n)，以后每次不是left變，就是right變，當(dāng)最后變到left>right就說(shuō)明查找失敗，所以其也作為循環(huán)結(jié)束的一個(gè)條件。第1次查找范圍(left=1,right=n)......第n次查找范圍left>right,查找失敗問(wèn)題5二分查找2.算法實(shí)現(xiàn)設(shè)計(jì)折半查找子程序halfsearch在查找前，要完成flag、wz、left、right和middle（中間位置）的初始化。完成初始化問(wèn)題5二分查找2.算法實(shí)現(xiàn)設(shè)計(jì)折半查找子程序halfsearch開(kāi)始查找后，是取中間位置的值（即a[middle]）和key比較，若相等，則狀態(tài)變量flag=1；否則還要判斷a[middle]是小于還是大于key值，從而決定是left變化還是right