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

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